The Shadow Array#13057
Sign in

The Shadow Array

2 seconds
256 megabytes
Hard

For an array of positive integers, its shadow array of length is defined as follows:

h_i = \min\left(\max_{j=1}^{i} a_j, \max_{j=i}^{n} a_j\right)

You are given the shadow array . Your task is to find the number of valid original arrays consisting of positive integers that could have produced .

Since this number can be very large, output it modulo 10^9 + 7.

Input

The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.

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

The second line of each test case contains integers h_1, h_2, \dots, h_n (1 \le h_i \le 10^9) — the elements of the shadow array .

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

Output

For each test case, output a single integer — the number of valid original arrays modulo 10^9 + 7.

Examples

Example 1

Loading
Loading

Note

In the first test case, h = [2, 2, 2]. There are exactly valid original arrays that produce this shadow array:

  • a = [2, 1, 2]

  • a = [2, 2, 2]

Scoring

  • Subtask ( points): \sum n \le 8 and h_i \le 8.

  • Subtask ( points): \sum n \le 1000 and h_i \le 100.

  • Subtask ( points): No additional constraints.