Unique Bib Allocation

Given an integer N, count the number of valid allocations for N participants. Each allocation assigns a unique bib number to every participant such that the sum of the bib numbers of any subset of participants is distinct. It turns out that the number of valid allocations is exactly \(N! \mod (10^9+7)\).

For example, if N = 3, the answer is 3! = 6.

inputFormat

The first line of input contains an integer T (the number of test cases). Each of the following T lines contains a single integer N (1 ≤ N ≤ 10⁵) representing the number of participants.

outputFormat

For each test case, output one line containing the number of valid allocations, i.e. \(N! \mod (10^9+7)\).

3
1
2
3

1
2
6