AOJ 5005 - Clarke and tree

Clarke and tree

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on HDU. Original ID: 5629
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

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

Source

BestCoder Round #72 (div.1)