대수학 협업

군론을 연구하는 사람들과 선형대수를 연구하는 사람들이 두 이론을 합치려고 한다. 군론에서는 전단사 함수, 즉 순열이 중요한 역할을 한다. 유한집합 $A$에 대해 함수 $\sigma : A \to A$가 $A$의 순열이라는 것은, 모든 $a \in A$에서 $\sigma(\rho(a)) = a$이고 $\rho(\sigma(a)) = a$인 함수 $\rho : A \to A$가 존재한다는 뜻이다.

팀의 나머지 절반인 선형대수 전문가는 멱등 함수를 많이 다룬다. 멱등 함수는 3차원 게임에서 그림자를 계산할 때 쓰는 사영으로 나타나고, 추이 폐포 같은 폐포 연산자로도 나타난다. 함수 $p : A \to A$가 멱등이라는 것은 모든 $a \in A$에서 $p(p(a)) = p(a)$가 성립한다는 뜻이다.

두 팀은 유한집합 $A$의 순열 중 멱등이 아닌 것이 몇 개인지 알고 싶다. 그 개수가 $A$의 크기에만 달려 있다는 사실은 이미 알아냈다. 크기 $n$이 주어질 때, 원소가 $n$개인 집합의 순열 중 멱등이 아닌 것의 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 100$). 이어지는 $t$개의 줄에 집합의 크기 $n$이 한 줄에 하나씩 주어진다 ($1 \le n \le 10^5$).

각 테스트 케이스마다 원소가 $n$개인 집합의 순열 중 멱등이 아닌 것의 개수를 $10^9 + 7 = 1000000007$로 나눈 나머지를 한 줄에 출력한다.