#168 다다스의 부분수열

Loading problem...

Preparing the statement, recent submissions, and submit form.

#168 다다스의 부분수열

Authors: dyppp

Statement

길이 $N$ 의 수열 $A$ 가 주어진다.

어떤 수열 $B$ 에 대해, $B$ 에서 서로 인접하지 않은 원소 몇 개를 골라 그 합을 최대화하는 문제를 생각하자. 고른 원소가 없어도 되며, 이때 합은 $0$ 이다. 이 최댓값을 $g(B)$ 라고 하자.

예를 들어 $B=(3,1,4,1)$ 이면, 첫 번째 원소와 세 번째 원소를 골라 합 $7$ 을 만들 수 있고, 이것이 최댓값이다. 따라서 $g(B)=7$ 이다.

다다스는 이 문제가 너무 쉽다고 생각했다. 그래서 다다스는 $A$ 의 모든 비어 있지 않은 $2^N-1$ 가지의 부분수열 $B$ 에 대한 $g(B)$ 의 합을 구하는 문제로 바꾸었다.

즉, 다음 값을 구하여라.

\sum_{\emptyset \ne B \preceq A} g(B)

여기서 $B \preceq A$ 는 $B$ 가 $A$ 의 부분수열임을 의미한다.

답을 $1\,000\,000\,007$ 로 나눈 나머지를 출력하여라. 출력할 때는 편의를 위해 답*2를 출력한다

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

모든 비어 있지 않은 부분수열 $B$ 에 대한 $g(B)$ 의 합을 $1\,000\,000\,007$ 로 나눈 나머지를 출력한다. 출력할 때는 편의를 위해 답*2를 출력한다

Sample 1

Input

2
1 2

Output

비어 있지 않은 부분수열은 $(1)$ , $(2)$ , $(1,2)$ 이다.

부분수열 $(1,2)$ 에서는 두 원소가 서로 인접하므로 둘을 동시에 고를 수 없다. 따라서 $g(1,2)=2$ 이다.

그러므로 답은 $1+2+2=5$ 이다. 출력할 때는 편의를 위해 답*2를 출력해야 하므로 $10$ 을 출력하면 된다.

Sample 2

Input

3
1 2 3

Output

비어 있지 않은 부분수열 $7$ 개의 $g$ 값은 각각 다음과 같다.

1,\ 2,\ 3,\ 2,\ 3,\ 3,\ 4

따라서 답은 $18$ 이다. 출력할 때는 편의를 위해 답*2를 출력해야 하므로 $18$ 을 출력하면 된다.

Sample 3

Input

4
3 1 4 1

Output