N-Dimensional Grid

You are given an n-dimensional grid in which the dimensions of the grid are a1 × a2 × ⋯× ana_1 \times a_2 \times \dots \times a_n. Each cell in the grid is represented as an n-tuple (x1, x2, …, xn)(1 ≤ xi ≤ ai)(x_1, x_2, \dots, x_n) (1 \le x_i \le a_i).

Two cells are considered to be adjacent if the Manhattan Distance between them is equal to 1. The Manhattan Distance between two cells X(x1, x2, …, xn)X(x_1, x_2, \dots, x_n) and Y(y1, y2, …, yn)Y(y_1, y_2, \dots, y_n) is equal to: ∣x1 − y1∣ + ∣x2 − y2∣ + … + ∣xn − yn∣|x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|.

Your task is to count how many pairs of cells are adjacents. Can you? Two pairs of cells are considered the same if they include the same cells, i.e the pair (c1, c2)(c_1, c_2) is the same as (c2, c1)(c_2, c_1).

Input

The first line contains an integer T(1 ≤ T ≤ 100)T (1 \le T \le 100) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105)(1 \le n \le 10^5), in which n is the number of dimensions of the grid. Then a line follows containing n integers a1, …, an(1 ≤ ai ≤ 105)a_1, \dots, a_n (1 \le a_i \le 10^5), in which ai is the size of the ith dimension.

The sum of n overall test cases does not exceed 6 × 1066 \times 10^6.

Output

For each test case, print a single line containing the number of pairs of adjacent cells modulo 109 + 7.

Example

Input

1
3
1 2 3

Output

7

题意：

在一个 nn 维空间中的一个点可以表示为一个 nn 元组 (a1,a2,a3,a4,a5,…,an)(a_1,a_2,a_3,a_4,a_5, \dots ,a_n)
两个格子相邻时：这两个格子的曼哈顿距离为1,即对于两个点

X(x1, x2, …, xn),Y(y1, y2, …, yn)X(x_1, x_2, \dots , x_n) , Y(y_1, y_2, \dots , y_n)

有

∣x1 − y1∣ + ∣x2 − y2∣ + … + ∣xn − yn∣|x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|

在给出每个维度的size后，求这个空间中有多少对相邻的格子。

解：

从一维开始，n个格子有n-1对相邻。
现在的答案为ans[1]，现在一共有num[1]个格子

当多增加一维时，若这一维的size为m（就有m个前一维），则当前一共有 ans[1]×mans[1] \times m 个与前一维一样的（前一维复制m遍）
然后每一个维与维维之间有 (m−1)×num[1](m-1)\times num[1] 个
所以新的答案ans[2]是 ans[2]×m+(m−1)×num[1]ans[2] \times m + (m-1)\times num[1]
然后当前一共有 n×mn\times m 个格子,num[2]=n*m

再加一维size为k的：ans[3]=ans[2]*k+(k-1)*num[2]

推广这个规律，

ans[i]=ans[i−1]×a[i]+num[i−1]×a[i]−1ans[i] = ans[i-1] \times a[i] + num[i-1] \times a[i] - 1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef long long ll;
ll ans;
const ll MOD = 1000000000 + 7;
int a[100000 + 10];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(a,0, sizeof(a));
		int n;
		ans = 0;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		ll num = a[0];
		ans = a[0] - 1;//第一维
		for (int i = 1; i < n; i++)
		{
			ans = ans * a[i];
			ans %= MOD;
			ans = ans + (a[i] - 1)*num;
			num *= a[i];
			num %= MOD;
			ans %= MOD;
		}
		printf("%lld\n", ans);
	}
}