In computer Science there is common need to generate random permutation. It can be seen as the shuffle of the numbers. Start with sorted permutation of n, at each step select the random no between 1 to n and put it at front. after doing n steps you can write shuffle sequence like {p1,p2,p3 ,...,pn} where at i th step you select pi number and put it at the front. CS people wonders how many shuffle sequence give the original sorted order?
Note that length of the shuffle sequence is same as length of the permutation.
*First line contains 't', the no of test cases. *
*Each test contains 'n', the length of the shuffle sequence. *
You need to print the no of shuffle sequences which gives original sorted permutation . This number can be very large so print answer%1000000007
1<=t<=100000
1<=n<=1000
Author : Kandarp Joshi
Here n=2
so initial permutation is 1 2
we have two possible shuffle sequences {1,1} and {2,1}
which gives original permutation back
applying {2,1} shuffle sequence on permutation 1 2
after first step you get 2 1
after second step you get 1 2
