this is a programming practice called 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) fromA_{0}toA_{N}.You must write the numbers on a sheet of paper, such thatA_{0}is written first. The other numbers are written according to an inductive rule — afterA_{i-1}numbers have been written in a row, thenA_{i}can be written at either end of the row. That is, you first writeA_{0}, and thenA_{1}can be written on its left or right to makeA_{0}A_{1}orA_{1}A_{0}, and so on.A_{i}must be written before writingA_{j}, for everyi < j.For a move in which you write a numberA_{i}(i>0), your points increase by the product ofA_{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 theN + 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 allN + 1 numbers, when we read from left to right, there exists some positioni, at which the gameplays havea_{j}anda_{k}written at thei^{th}position such thatj ≠ 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 modulo10^{9}+ 7.

Input:

The first line of the input contains an integerT denoting the number of test cases.The first line of each test case contains a single integerN.The second line containsN + 1 space-separated integers denotingA_{0}toA_{N}.

Output:

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

Constraints:

1 ≤T ≤101 ≤N ≤10^{5}1 ≤A_{i}≤10^{9}

Example

Input:

2

1

1 2

2

1 2 1

Output:

4

14

Explanation

There are2 possible gameplays.A_{0}A_{1}which gives score of2 andA_{1}A_{0}which also gives score of2. So the answer is2 + 2 = 4

**********************************************

done.

my code gives the correct answer everytime but when i submit, it always says wrong answer.

i don't know what is wrong. please help.

here is my code:

Code:#include<iostream> #include<vector> #include<cmath> #include<string> using namespace std; int length = 0; unsigned long long sum = 0; void solve(const unsigned long long & l, const unsigned long long & r, const vector<unsigned long long> & v, const int & left, const unsigned long long & prevSum) { if (left == 0) { sum += prevSum; return; } sum += prevSum *((unsigned long long)pow(2,left)); int next = length - left; unsigned long long subSum1 = r*v[next]; solve(l, v[next], v, left - 1, subSum1); unsigned long long subSum2 = l*v[next]; solve(v[next], r, v, left - 1, subSum2); } unsigned long long findSum(const vector<unsigned long long> & v) { unsigned long long l = v[0]; unsigned long long r = v[1]; solve(l, r, v, length - 2, l*r); l = v[1]; r = v[0]; solve(l, r, v, length - 2, l*r); return sum % 1000000007; } int main() { int T; cin >> T; while (T--) { cin >> length; ++length; unsigned long long num; vector<unsigned long long> v = vector<unsigned long long>(); for (int i = 0; i < length; i++) { cin >> num; v.push_back(num); } printf("%llu\n",findSum(v)); sum = 0; } }