408044: GYM102966 H Hamsters Training

H. Hamsters Trainingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Malva the marshmallow adopted a group of $$$N$$$ super-smart hamsters. Since Malva is super responsible, he keeps a strict quarantine and has plenty of time at home. In the middle of his boredom, Malva came up with an idea: he would train his hamster friends!

After some time of thinking, Malva decided to start the training with a game whose rules are listed below:

• Malva cuts $$$N^2$$$ cards and fills $$$N$$$ cards with the number 1, $$$N$$$ with the number 2, $$$N$$$ with the number 3, and so on.
• Malva has a whistle that plays for indicating the hamsters it is time to move on. At that moment, the hamsters take a card –whichever they want– and make a line with the $$$N$$$ cards.
• The formed line may be considered succeeded or failed. Only in the former case, Malva will reward the rodents. Because these cute animals are brilliant and really want the prize, you can be sure they will never fail.
• For a configuration to be successful, every card in the line must be greater than or equal to all the numbers to the left.
• Once finished and evaluated the line, the rodents give the cards back and prepare for the next turn.

Malva has a complete training plan for the tiny animals, and this game is only the beginning of it. To approximate the time it could take, he wants to know how many valid configurations there are. Your mission, if you choose to accept it, is to help Malva to get that number.Input

The first line of input contains a single integer number $$$T$$$ ($$$0 < T \leq 10^4$$$), representing the number of cases. Each of the following $$$T$$$ lines contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of super-smart hamsters Malva adopted.

Output

For each case, print in a distinct line the number of valid lines the hamsters can create. Because that number could be huge, print it modulo $$$10^9 + 7$$$.

ExampleInput

3
2
4
312

Output

3
35
653353651