The Election of Noakhali

Recently, Noakhali became a sovereign state. As a result, the first parliamentary election of the Republic of Noakhali is going to be held soon.

Sajid is a polling officer at an election center. There will be exactly $N$ queues of voters and Sajid knows exactly how many voters will be in each queue. At a time, only one person from the front of a non-empty queue will come and give their votes. After that, they will be headed home. The order of persons in each queue is known beforehand. As it’s the first election of their newborn nation, Sajid wants to know every possible situation and be prepared for them. As part of that, he wants to know in how many ways voters can give their votes.

Two ways are said to be different if the sequence of voters giving votes is different.

Input

First line of input will contain an integer $T$ ($1\leq T \leq 10^{6}$), the number of test cases.

Next $2\times T$ lines will describe the test cases.

First line of each test case will contain an integer $N(1 \leq N \leq 10^{6})$, the number of queues.

Second line of each test case will contain $N$ space separated integers $A_{1}, A_{2}, A_{3},\dots,A_{N} ~(~0 \leq A_{i} \leq 10^{6}~)$, where $A_{i}$ is the number of voters in $i$-th queue.

The sum of $N$ over all test cases does not exceed $10^{6}$.

The sum of the voters of the queues of a single test case does not exceed $10^{6}$.

Output

For each test cases, print the answer on a separate line.

As the answer can be really big, print it modulo $10^{9} + 7$.

Sample

1
2
2 1

3