Photo Album Derangements

You are given a single integer n representing the number of photo albums. A derangement is a permutation of the albums such that no album remains in its original position. Your task is to compute the number of possible derangements of these n photo albums modulo 10^9 + 7.

The number of derangements can be computed using the recurrence relation below, written in LaTeX format:

\(D(n) = (n-1) \times (D(n-1) + D(n-2)) \)

with the initial conditions:

\(D(1) = 0\) and \(D(2) = 1\).

For example:

• When n = 1, the answer is 0.
• When n = 2, the answer is 1.
• When n = 3, the answer is 2.
• When n = 4, the answer is 9.

Your program should read its input from stdin and write the output to stdout.

inputFormat

The input begins with an integer T indicating the number of test cases. Each test case consists of a single line containing an integer n (where n ≥ 1).

Example:

3
1
2
3

This represents 3 test cases with n = 1, n = 2, and n = 3 respectively.

outputFormat

For each test case, output a single integer representing the number of derangements of n photo albums modulo 1000000007, each on a new line.

Example corresponding to the above input:

0
1
2

## sample

3
1
2
3

0
1
2

</p>