Count derangements

A Derangement is a permutation of ‘N’ elements, such that no element appears in its original position. For example, an instance of derangement of {0, 1, 2, 3} is {2, 3, 1, 0}, because 2 present at index 0 is not at its initial position which is 2 and similarly for other elements of the sequence.

Given a number ‘N’, find the total number of derangements possible of a set of 'N’ elements.

Note:

The answer could be very large, output answer %(10 ^ 9 + 7).

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line and the only line of each test case contains an integer ‘N’ denoting the number of elements whose derangements are to be counted.

Output Format:

For each test case, return the total number of derangements of a set of ‘N’ elements. 

Note:

You don't need to print anything, it has been already taken care of. Just implement the given function. 

Constraints:

1 <= T <= 100
1 <= N <= 3000

Time limit: 1 sec