길이 의 수열 가 주어진다.
어떤 수열 에 대해, 에서 서로 인접하지 않은 원소 몇 개를 골라 그 합을 최대화하는 문제를 생각하자. 고른 원소가 없어도 되며, 이때 합은 이다. 이 최댓값을 라고 하자.
예를 들어 이면, 첫 번째 원소와 세 번째 원소를 골라 합 을 만들 수 있고, 이것이 최댓값이다. 따라서 이다.
다다스는 이 문제가 너무 쉽다고 생각했다. 그래서 다다스는 의 모든 비어 있지 않은 가지의 부분수열 에 대한 의 합을 구하는 문제로 바꾸었다.
즉, 다음 값을 구하여라.
여기서 는 가 의 부분수열임을 의미한다.
답을 로 나눈 나머지를 출력하여라. 출력할 때는 편의를 위해 답*2를 출력한다
입력은 다음과 같은 형식으로 주어진다.
모든 비어 있지 않은 부분수열 에 대한 의 합을 로 나눈 나머지를 출력한다. 출력할 때는 편의를 위해 답*2를 출력한다
비어 있지 않은 부분수열은 , , 이다.
부분수열 에서는 두 원소가 서로 인접하므로 둘을 동시에 고를 수 없다. 따라서 이다.
그러므로 답은 이다. 출력할 때는 편의를 위해 답*2를 출력해야 하므로 을 출력하면 된다.
비어 있지 않은 부분수열 개의 값은 각각 다음과 같다.
따라서 답은 이다. 출력할 때는 편의를 위해 답*2를 출력해야 하므로 을 출력하면 된다.
