Valid Mentorship Configurations

In this problem, you are given an integer number of employees for several test cases. For each test case, you need to calculate the number of valid mentorship configurations. A valid configuration is one in which no employee mentors themselves -- this is equivalent to computing the number of derangements. The recurrence relation for derangements is given by

with the initial conditions $$D(1)=0$$ and $$D(2)=1$$.

Given multiple test cases, your task is to compute the derangement number for each input value modulo $$10^9+7$$ and output the result on a separate line.

inputFormat

The input starts with a single integer (T) ((1 \le T \le 10^5)) representing the number of test cases. This is followed by (T) lines, each containing an integer (n) ((1 \le n \le 10^5)), representing the number of employees.

outputFormat

For each test case, output one line containing the number of valid mentorship configurations (i.e. derangements) modulo (10^9+7).## sample

3
2
3
4

1
2
9