Rupsa and the Game

Rupsa and the Game

Princess Rupsa saw one of her friends playing a special game. The game goes as follows:

N+1 numbers occur sequentially (one at a time) from A0 to AN.

You must write the numbers on a sheet of paper, such that A0 is written first. The other numbers are written according to an inductive rule — after Ai-1 numbers have been written in a row, then Ai can be written at either end of the row. That is, you first write A0, and then A1 can be written on its left or right to make A0A1 or A1A0, and so on.
Ai must be written before writing Aj, for every i < j.
For a move in which you write a number Ai (i>0), your points increase by the product of Ai and its neighbor. (Note that for any move it will have only one neighbor as you write the number at an end).
Total score of a game is the score you attain after placing all the N + 1 numbers.
Princess Rupsa wants to find out the sum of scores obtained by all possible different gameplays. Two gameplay is different if after writing down all N + 1 numbers when we read from left to right, there exists some position i, at which the gameplay have aj and ak written at the ith position such that j ≠ k. But since she has recently found her true love, a Frog Prince, and is in a hurry to meet him, you must help her solve the problem as fast as possible. Since the answer can be very large, print the answer modulo 109 + 7.

Input

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains a single integer N.
The second line contains N + 1 space-separated integers denoting A0 to AN.

Output

For each test case, output a single line containing an integer denoting the answer.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109

Solution:

        #include<stdio.h>
        #define TOPES 1000000007
        #define imum 100005
        char fast_c;
        unsigned long fast_j;
        unsigned long fast_in() {
        for(fast_c=getchar_unlocked(); fast_c<'0'||fast_c>'9'; fast_c=getchar_unlocked());
        for(fast_j=0; fast_c>='0'&&fast_c<='9'; fast_c=getchar_unlocked())
        fast_j=(fast_j<<1)+(fast_j<<3)+(fast_c-'0');
        return fast_j;
        }
        int main()      {
        unsigned long t, n, i, a[imum];
        unsigned long long ans, sum[imum], pow[imum];
        for(pow[0]=1, i=1; i<imum; i++)
        pow[i]=(pow[i-1]<<1)%TOPES;
        for(t=fast_in(); t; t--){
        for(n=fast_in(), i=0; i<=n; i++)
        a[i]=fast_in();
        for(sum[0]=(a[0]<<1)%TOPES, i=1; i<=n; i++)
        sum[i]=(sum[i-1]+a[i]*pow[i])%TOPES;
        for(ans=0,i=1; i<=n; i++)
        ans=((ans<<1)+(a[i]*sum[i-1])%TOPES)%TOPES;
        printf("%llu\n",ans);
        }
        return 0;
        }