Clarke is a patient with multiple personality disorder. One day, Clarke turned into a CS, did a research on data structure.
Now Clarke has $n$ nodes, he knows the degree of each node no more than $a_i$. He wants to know the number of ways to choose some nodes to compose to a tree of size $s(1 \le s \le n)$.
Input
The first line contains one integer $T(1 \le T \le 10)$, the number of test cases.
For each test case:
The first line contains an integer $n(2 \le n \le 50)$.
Then a new line follow with $n$ numbers. The $i$th number $a_i(1 \le a_i < n)$ denotes the number that the degree of the $i$th node must no more than $a_i$.
Output
For each test case, print a line with $n$ integers. The $i$th number denotes the number of trees of size $i$ modulo $10^9+7$.
Sample Input
1
3
2 2 1
Sample Output
3 3 2
Hint:
At first we know the degree of node 1 can not more than 2, node 2 can not more than 2, node 3 can not more than 1. So
For the trees of size 1, we have tree ways to compose, are 1, 2 and 3. i.e. a tree with one node.
For the trees of size 2, we have tree ways to compose, are 1-2, 1-3, 2-3.
For the trees of size 3, we have two ways to compose, are 1-2-3, 2-1-3.
