다다스의 부분수열

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

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

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

다다스는 이 문제가 너무 쉽다고 생각했다. 그래서 다다스는 $A$의 모든 비어 있지 않은 $2^N-1$ 가지의 부분수열 $B$에 대한 $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를 출력한다

• $1 \le N \le 200\,000$.
• $1 \le A_i \le 10$ ($1 \le i \le N$).
• 입력으로 주어지는 모든 값은 정수이다.