**Spliting Balls solution codechef** – There are $N$ balls in a bag. Initially, the $i_{th}$ ball has a number $A_{i}$ on it.

## Spliting Balls solution codechef

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 $1_{100}$ seconds. Since the final number of balls can be huge, output the answer modulo $1_{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},…,A_{N}$, denoting the initial number written on the balls.

## Spliting Balls solution codechef

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

### Constraints

- $1≤T≤1_{4}$
- $1≤N≤2⋅1_{5}$
- $1≤A_{i}≤1_{6}$
- The sum of $N$ over all test cases won’t exceed $2⋅1_{5}$.

### Sample 1:

3 1 2 2 1 2 3 3 1 3

2 3 13

## Spliting Balls solution codechef

**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$.