codeChef :Rupsa and the Game Problem Code: RGAME

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 A₀ to A_N.
• You must write the numbers on a sheet of paper, such that A₀ is written first. The other numbers are written according to an inductive rule — after A_i-1 numbers have been written in a row, then A_i can be written at either end of the row. That is, you first write A₀, and then A₁ can be written on its left or right to make A₀A₁ or A₁A₀, and so on.
• A_i must be written before writing A_j, for every i < j.
• For a move in which you write a number A_i (i>0), your points increase by the product of A_i and its neighbour. (Note that for any move it will have only one neighbour 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 gameplays are different, if after writing down all N + 1 numbers, when we read from left to right, there exists some position i, at which the gameplays have a_j and a_k written at the i^th 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 10⁹ + 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 A₀ to A_N.

Output

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

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹

Sub tasks

• Subtask #1: 1 ≤ N ≤ 10 (10 points)
• Subtask #2: 1 ≤ N ≤ 1000 (20 points)
• Subtask #3: Original Constraints (70 points)

Example

Input:
2
1
1 2
2
1 2 1

Output:
4
14

Explanation

There are 2 possible gameplays. A₀A₁ which gives score of 2 and A₁A₀ which also gives score of 2. So the answer is 2 + 2 = 4 




SOLUTION IN JAVA:   

 import java.util.*;
public class Rupsa {
public static void main(String []args){
    Scanner sc=new Scanner(System.in);
    long mod=1000000007L;
    int t=sc.nextInt();int[] art=new int[t];
    for(int i=0;i<t;i++){
        int N=sc.nextInt();
        int []ar=new int[N+1];long l,m=0,n=0,p=1;
    //int jl=2,kl=1;
  
        for(int j=0;j<N+1;j++){
          
            ar[j]=sc.nextInt();
        }
        long o=ar[0];
            for(int j=1;j<N+1;j++){
                long k=2;
                m*=2;
            k=(k*o*ar[j])%mod;
            m=(m+k)%mod;
            o=(o+p*ar[j])%mod;
                p=(p*2)%mod;
              
          
        }
        int    m1=(int)m%1000000007;
        art[i]=m1;
    }
    for(int h:art){
        System.out.println(h);
    }
}
}