### PROBLEM

You are given an array A consisting of N integers. For each number A_i, i from 2 to N, you can decide to put either a `+, plus`

or a `*, multiplication`

sign before it. After putting the N-1 signs, you evaluate the expression. You have to find the sum of the values of the all 2^{N-1} such expressions. Output your answer modulo 10^9 + 7.

Note that `multiplication`

sign has higher priority than `plus`

sign. For example, the value of the expression 2 + 2 * 2 will be 2 + 4 = 6.

### SOLUTION

The problem can be solved using dynamic programming. Let dp[i] denote the sum of values of expressions made using first i elements of the array. Our answer will be dp[n].

We can find the recurrence relation for dp[i] as follows. Let j be the largest index \leq i, such that we decide to put a `plus`

sign before A_j. That means that all the signs between the numbers from A_j to A_i are all `multiplication`

signs. Let p[j,i] denote the product of numbers A_k where j \leq k \leq i. Note that dp[j - 1] denotes the sum of values of the 2^{j-2} expressions of first j-1 values of array A. We add value p[j.i] in each of these expressions. So, overall contribution due to a fixed j will be dp[j-1] + p[j.i] \cdot 2^{j-2}.

Hence, the recurrence relation for dp[i] will be as follows.

For i > 1,

Calculating dp using this expression will take quadratic time in terms of N, the size of the array A. We want to compute it faster.

Let prod[i] denote the product of first i elements of array A, modulo 10^9 + 7. We can write p[j.i] as \frac{prod[i]}{prod[j-1]}, i.e. prod[i] * prod[j - 1]^{-1} modulo 10^9 + 7. So, the recurrence relation now becomes.

Suppose you maintain a prefix sum dp array sdp[i] which will store the sum of dp[0] + dp[1] + dp[2] + \dots + dp[i-1], and a prefix sum array extra[i] which stores sum of prod[j - 1]^{-1} \cdot 2^{j-2} for j from 1 to i. After this, you can write your updated recurrence relation as follows.

You can maintain arrays dp, sdp, prod, extra in a single iteration over the array. Overall time complexity of this will be \mathcal{O}(n \cdot \log{10^9 + 7}). The \log{10^9 + 7} is accounted towards finding the inverse of a number modulo 10^9 + 7.