405467: GYM101968 C Function

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$$$.

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$$$.

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

3
2
1 1
3
1 2 3
5
1 3 5 7 11

4
22
295