Chef has a sequence of $N integers A_{1}, A_{2},\dots, A_{N}. He defines a function f(i, j)$ as follows:

$f(i, j) = A_{i} + max(A_{i}, A_{i + 1}) + max(A_{i}, A_{i + 1}, A_{i + 2}) + \dots + max(A_{i}, A_{i + 1}, \dots, A_{j})$

Chef tries to find the sum of f(i, j) over all (i, j) such that 1 ≤ i ≤ j ≤ $N (i.e \sum\limits_{i=1}^n \sum\limits_{j=i}^nf(i, j)),$ but fails. Can you help him find the sum?

Since the sum can be very large, find it modulo (10^{9} + 7).

Note: Since the size of the input and output is large, please use fast input-output methods.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N.
• The second line contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$.

------ Output Format ------

For each test case, print a single line containing one integer - the required sum $i.e \sum\limits_{i=1}^n \sum\limits_{j=i}^nf(i, j) modulo (10^{9} + 7)$.

------ Constraints ------

$1 ≤ T ≤ 5\cdot 10^{3}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------
3
2
1 2
3
1 2 3
4
5 4 1 3

----- Sample Output 1 ------
6
20
82

----- explanation 1 ------
Test case $1$:

• $f(1, 1) = A_{1} = 1$.
• $f(1, 2) = A_{1} + max(A_{1}, A_{2}) = 1 + max(1, 2) = 1 + 2 = 3$.
• $f(2, 2) = A_{2} = 2$.

Hence the required sum $= 1 + 3 + 2 = 6$.

Test case $2$:

• $f(1, 1) = A_{1} = 1$.
• $f(1, 2) = A_{1} + max(A_{1}, A_{2}) = 1 + max(1, 2) = 1 + 2 = 3$.
• $f(1, 3) = A_{1} + max(A_{1}, A_{2}) + max(A_{1}, A_{2}, A_{3}) = 1 + max(1, 2) + max(1, 2, 3) = 1 + 2 + 3 = 6$.
• $f(2, 2) = A_{2} = 2$.
• $f(2, 3) = A_{2} + max(A_{2}, A_{3}) = 2 + max(2, 3) = 2 + 3 = 5$.
• $f(3, 3) = A_{3} = 3$.

Hence the required sum $= 1 + 3 + 6 + 2 + 5 + 3 = 20$.

见题面

见题面