Algebraic Teamwork

Researchers in group theory and researchers in linear algebra want to combine their two theories. In group theory, permutations, also called bijective functions, matter a lot. For a finite set $A$, a function $\sigma : A \to A$ is a permutation of $A$ if and only if there is a function $\rho : A \to A$ such that $\sigma(\rho(a)) = a$ and $\rho(\sigma(a)) = a$ hold for every $a \in A$.

The other half of the team, the linear algebra experts, work with idempotent functions a lot. They appear as projections when a 3D game computes shadows, and as closure operators such as the transitive closure. A function $p : A \to A$ is idempotent if and only if $p(p(a)) = p(a)$ holds for every $a \in A$.

The team wants to know how many permutations of a finite set $A$ are not idempotent. They already found that this count depends only on the size of $A$. Given a size $n$, count the permutations of a set of $n$ elements that are not idempotent.

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Each of the next $t$ lines contains one set size $n$ ($1 \le n \le 10^5$).

For each test case, print one line with the number of permutations of a set of $n$ elements that are not idempotent, modulo $10^9 + 7 = 1000000007$.