There are N balls in a bag. Initially, the i^{th} ball has a number A_{i} on it.

In one second, a ball with number k (k>1), dissociates into k balls, where each of the k balls has number (k-1) written on it.
If k = 1, there is no change on the state of the ball.

Find the number of balls in the bag after 10^{100} seconds. Since the final number of balls can be huge, output the answer modulo 10^{9}+7.

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

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer N, denoting the number of balls in the bag.
• The next line contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N},$ denoting the initial number written on the balls.

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

For each test case, output on a new line, the number of balls in the bag after 10^{100} seconds. Since the final number of balls can be huge, output the answer modulo 10^{9}+7.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------
3
1
2
2
1 2
3
3 1 3

----- Sample Output 1 ------
2
3
13

----- explanation 1 ------
Test case $1$: Initially, the balls in the bag are $\{2\}$.
- After $1$ second: The ball with number $2$ dissociates into two balls with number $1$. Thus, the bag looks like $\{1, 1\}$.

No more dissociation is possible after this. Thus, the final number of balls is $2$.

Test case $2$: Initially, the balls in the bag are $\{1, 2\}$.
- After $1$ second: The ball with number $2$ dissociates into two balls with number $1$. Thus, the final bag looks like $\{1, 1, 1\}$.

No more dissociation is possible after this. Thus, the final number of balls is $3$.

Test case $3$: Initially, the balls in the bag are $\{3, 1, 3\}$.
- After $1$ second: The balls with number $3$ dissociates into three balls with number $2$. Thus, the bag looks like $\{2, 2, 2, 1, 2, 2, 2\}$.
- After $2$ seconds: The balls with number $2$ dissociates into two balls with number $1$. Thus, the bag looks like $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$.

No more dissociation is possible after this. Thus, the final number of balls is $13$.

见题面

见题面