405177: GYM101810 E N-Dimensional Grid

You are given an n-dimensional grid in which the dimensions of the grid are a₁ × a₂ × ... × a_n. Each cell in the grid is represented as an n-tuple (x₁, x₂, ..., x_n) (1 ≤ x_i ≤ 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(x₁, x₂, ..., x_n) and Y(y₁, y₂, ..., y_n) is equal to: |x₁ - y₁| + |x₂ - y₂| + ... + |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 (c₁, c₂) is the same as (c₂, c₁).

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

The first line of each test case contains an integer n (1 ≤ n ≤ 10⁵), in which n is the number of dimensions of the grid. Then a line follows containing n integers a₁, ..., a_n (1 ≤ a_i ≤ 10⁵), in which a_i is the size of the i^th dimension.

The sum of n overall test cases does not exceed 6 × 10⁶.

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

1
3
1 2 3

7

The absolute value |x| of a real number x is the non-negative value of x without regard to its sign. Namely, |x| = x for a positive x, |x| =  - x for a negative x (in which case  - x is positive), and |0| = 0. For example, the absolute value of 3 is 3, and the absolute value of  - 3 is also 3. The absolute value of a number may be thought of as its distance from zero.