Algebraic Teamwork#7695

Algebraic Teamwork

1 second

128 megabytes

Medium

The great pioneers of group theory and linear algebra want to cooperate and combine their theories. In group theory, permutations (also known as bijective functions) play an important role. For a finite set $A$ , a function $σ : A \to A$ \sigma : A \rightarrow A is called a permutation of $A$ if and only if there exists a function $ρ : A \to A$ \rho : A \rightarrow A such that

σ (ρ (a)) = a and ρ (σ (a)) = a for all a \in A

\sigma(\rho(a)) = a \text{ and } \rho(\sigma(a)) = a \text{ for all } a \in A

The other half of the new team—the experts in linear algebra—work with idempotent functions. Such functions appear, for example, as projections when computing shadows in 3D games or as closure operators like the transitive closure. A function $p : A \to A$ p : A \rightarrow A is called idempotent if and only if

p (p (a)) = p (a) for all a \in A

p(p(a)) = p(a) \text{ for all } a \in A

To continue their joint research, they need your help. The team is interested in non-idempotent permutations of a given finite set $A$ . As a first step, they discovered that the result depends only on the size of the set. For a given size $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5), they want you to compute the number of permutations on a set of cardinality $n$ that are not idempotent.

\InputFileThe input starts with the integer $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100), the number of test cases. Then $t$ lines follow, each containing an integer $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) — the size of the set.

\OutputFileFor each test case, output the number of non-idempotent permutations on a set of cardinality $n$ , modulo $1000000007$ $= 1 0^{9} + 7$ = 10^9 + 7.

Examples

Example 1

Loading

σ : A \to A

ρ : A \to A

σ (ρ (a)) = a and ρ (σ (a)) = a for all a \in A

p : A \to A

p (p (a)) = p (a) for all a \in A

1 \leq n \leq 1 0^{5}

1 \leq t \leq 100

1 \leq n \leq 1 0^{5}

= 1 0^{9} + 7