405467: GYM101968 C Function

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Functiontime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Usually in competitive programming you're given a problem in which you need to design an efficient algorithm that solves that problem and implement it, but for this problem we decided to take it easy on you and just give you the algorithm, so that your only task is to implement it.

The algorithm goes like this:


f(l,r):
if l is equal to r then return a[l]
s = 0
for i = l to r: s = s + a[i]
return s + f(l+1,r) + f(l,r-1)

You are given the elements $$$a_i$$$, print the value of $$$f(1,n)$$$ modulo $$$10^9+7$$$.

Input

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 16$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), the number of elements of array $$$a$$$.

The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,...,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The sum of $$$n$$$ over all test cases doesn't exceed $$$4\times10^6$$$.

Output

For each test case, output a single line with the value of the function $$$f(1,n)$$$ modulo $$$10^9+7$$$.

ExampleInput
3
2
1 1
3
1 2 3
5
1 3 5 7 11
Output
4
22
295

加入题单

上一题 下一题 算法标签: