Consider an array A of length N. You know that for all 1 ≤ i ≤ N, 0 ≤ A_{i} ≤ 10^{5}. We construct an array B of length N-1 such that, for all 1 ≤ i ≤ N - 1, B_{i} = min(A_{i}, A_{i + 1}).

You are given the array B, you need to find out the total number of distinct arrays A which we could have used to construct the given array B.

The answer may be large, so you need to find it modulo 10^{9} + 7.

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

• First line will contain T, number of testcases. Then the testcases follow.
• The first line of each test case contains a single integer N
• The second line of each test case contains N-1 space separated integers - the i^{th} of which is B_{i}

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

For each testcase(in a new line), output the count of valid possibilities of array A modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$
$0 ≤ B_{i} ≤ 10^{5}$

----- Sample Input 1 ------
3
2
100
5
3 9 8 4
3
10 12
----- Sample Output 1 ------
199801
199983
199977
----- explanation 1 ------
Test Case $1$: All valid arrays $A$ are of the form $[100, x]$ and $[x, 100]$ where $100 ≤ x ≤ 10^{5}$. Therefore, the answer is $(10^{5} - 100) + (10^{5} - 100 + 1) = 199801$.

Test Case $3$: All valid arrays $A$ are of the form $[10, 12, x]$ and $[10, x, 12]$ where $12 ≤ x ≤ 10^{5}$. Therefore, the answer is $(10^{5} - 12) + (10^{5} - 12 + 1) = 199977$.

见题面

见题面