G. Symmetric Subarrays
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard and his secret partner believe arrays should be symmetric, and any asymmetric array is worthless. So, they defined a function $$$V(a)$$$ as the value of array $$$a$$$ as follows:

  • If the array is symmetric*, $$$V(a)$$$ is equal to the sum of all elements in $$$a$$$.
  • Otherwise, $$$V(a) = 0$$$.

Given an array $$$a$$$, calculate $$$\sum_{l=1}^{n}\sum_{r=l}^{n}V(a[l..r])$$$, where $$$a[l..r]$$$ is the subarray of $$$a$$$ from index $$$l$$$ to $$$r$$$.

Since the answer can be too large, print it modulo $$$10^9+7$$$.

* A symmetric array is an array that stays the same when reversed. More formally, in a symmetric array $$$a$$$ of $$$n$$$ integers, $$$a_i = a_{n+1-i}$$$ for $$$1 \le i \le n$$$. For example, the arrays $$$[1, 3, 1], [5, 9, 9, 5], [25]$$$ are symmetric, while $$$[1, 2], [4, 6, 4, 4]$$$ are not.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains the array length $$$n$$$ $$$(1 \le n \le 10^6)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print the answer modulo $$$10^9 + 7$$$.

Example
Input
5
3
1 2 1
4
8 9 9 8
5
18 5 18 7 29
2
1 2
5
100 100 100 100 100
Output
8
86
118
3
3500
Note

In the first test case, the subarrays of $$$[1, 2, 1]$$$ are $$$\{[1], [2], [1], [1, 2], [2, 1], [1, 2, 1]\}$$$.

Only $$$[1], [2], [1], [1, 2, 1]$$$ are symmetric, so the answer is their sum: $$$(1) + (2) + (1) + (1 + 2 + 1) = 8$$$.