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$

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.

h2. Restricţii

* $1 ≤ Q ≤ 10^5$
* $2 ≤ N ≤ 10^5$

* $1 ≤ Q ≤ 10^5^$
* $2 ≤ N ≤ 10^5^$

* For tests worth $10$ points, $2 ≤ N ≤ 20$.

* For tests worth another $50$ points, the sum of all $N$ in the input doesn't exceed $2*10^5$.

* For tests worth another $50$ points, the sum of all $N$ in the input doesn't exceed $200.000$.

h2. Exemplu