Derangements and Array Shuffle

In this problem, you are tasked with computing the number of derangements for a given integer ( n ) modulo ( 10^9+7 ). A derangement is a permutation of the elements such that no element appears in its original position. The recurrence relation to compute derangements is given by:

[ D(n) = (n-1) \times (D(n-1) + D(n-2)) \mod (10^9+7) ]

You will be given ( T ) test cases. For each test case, read an integer ( n ) and output the number of derangements for that value. Make sure to use efficient dynamic programming since ( n ) can be large.

inputFormat

The first line of input contains a single integer ( T ), the number of test cases. Each of the following ( T ) lines contains one integer ( n ).

outputFormat

For each test case, output the number of derangements of ( n ) modulo ( 10^9+7 ) on a new line.## sample

3
3
4
5

2
9
44