Problem Description
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 ai. He wants to know the number of ways to choose some nodes to compose to a tree of size s(1≤s≤n).
Input
The first line contains one integer T(1≤T≤10), the number of test cases.
For each test case:
The first line contains an integer n(2≤n≤50).
Then a new line follow with n numbers. The ith number ai(1≤ai<n) denotes the number that the degree of the ith node must no more than ai.
Output
For each test case, print a line with n integers. The ith number denotes the number of trees of size i modulo 109+7.
Sample Input
1
3
2 2 1
Sample Output
3 3 2