Secret Santa

Christmas is just around the corner and John's colleagues decided to organize a Secret Santa.

According to Google, Secret Santa is a Western Christmas tradition in which members of a group or community are randomly assigned a person to whom they give a gift.

There are $N$ students in John's class (him included) and he is very curious to know the number of possible ways Secret Santa can be organized. The number John asks being big, you should output it modulo $10^9 + 7$

Because there are a lot of John's on the planet, you will need to answer $Q$ queries regarding the possible ways Secret Santa can be organized in John's class. A valid way of organizing Secret Santa is a way such that no child gets gifts from two different children and there is no child who has to give a gift to himself/herself.

Input data

The first line of the input contains an integer $Q$, the number of queries.

Each of the following $Q$ lines contains an integer $N$.

Output data

The output will contain on each line the answer for the corresponding test case.

Constraints and clarifications

• $1 \leq Q \leq 10^5$
• $2 \leq N \leq 10^5$
• For tests worth $10$ points, $2 \leq N \leq 20$.
• For tests worth another $50$ points, the sum of all $N$ in the input doesn't exceed $200 \ 000$.

Example 1

stdin

4
5
6
9
12

stdout

44
265
133496
176214841