Solve the programming task below in a Python markdown code block.
Jim is doing his discrete maths homework which requires him to repeatedly calculate ^{n}C_{r}(n choose r) for different values of n. Knowing that this is time consuming, he goes to his sister June for help. June,  being a computer science student knows how to convert this into a computer program and generate the answers quickly. She tells him, by storing the lower values of ^{n}C_{r}(n choose r), one can calculate the higher values using a very simple formula. 

If you are June, how will you calculate ^{n}C_{r} values for different values of n?

Since ${}^{n}C_{r}$values will be large you have to calculate them modulo $\mathbf{10^{9}}$.  

Input Format 

The first line contains the number of test cases T. 

T lines follow each containing an integer n. 

Output Format 

For each n output the list of ^{n}C_{0} to ^{n}C_{n} each separated by a single space in a new line. If the number is large, print only the last 9 digits. i.e. modulo 10^{9}

Constraints 

1<=T<=200 

1<=n< 1000

Sample Input

3
2
4
5

Sample Output

1 2 1
1 4 6 4 1
1 5 10 10 5 1

Explanation 

For 2 we can check ^{2}C_{0}  ^{2}C_{1} and ^{2}C_{2} are 1, 2 and 1 respectively. The other inputs' answer follow similar pattern.