Limits 500ms, 512 MB

Megalomaniac Lex Luthor has heard about the famous "Fuchka" of AUST canteen. To have first hand experience of it, he along with his legion of doom members: Vandal savage, Bane, Cheetah, Mirror Master, Star Saphire and Deathstroke have come to visit the canteen.

The canteen manager is tech savvy. He has installed an app which can take requests for "Fuchka" from customers and also enlist if a new bowl of "Fuchka" has been prepared. The customer will get his or her "Fuchka" just after submitting the request, if "Fuchka" is prepared. The app will show "No Fuchka Found" if a customer requests for a plate of "Fuchka" but there is no plate of "Fuchka" present at that moment. A customer can request only one plate of "Fuchka" in a single request and only a single plate is served every time.

Lex knows his evil mates well. He knows Vandal savage will level the whole AUST canteen if he sees "No Fuchka Found" message ever. So, he is praying that each time an evil mate of him requests a plate of "Fuchka", there is an available one.

Lex, being a genius, also thinking about a problem. Say there are N persons who will request a plate of fuchka each. To meet their requirements , N plates should be prepared one by one. But they can not make the customer wait, so they will enlist each plate in the app and the customers will order them simultaneously. These "prepared" messages and customer requests are enlisted one by one in the app. Lex is thinking, in how many ways those requests and prepared messages for N customers can be enlisted so that no customer would ever see the "No Fuchka Given" message?

Help this genius, you "Brainiac" !!.

Input

First line of input will contain T, the number of test cases. 1<=T<=500.
Next T lines will contain one integer N each. 1<=N<=500.

Output

For each input integer N, print the answer modulo 1000000007 in a separate line.

Sample

InputOutput
3
2
8
10
2
1430
16796

Submit

Login to submit.

Statistics

91% Solution Ratio
BRUR_DivByZeroEarliest, Jan '18
nusuBotFastest, 0.0s
sakibalaminLightest, 131 kB
Tarik.amtolyShortest, 185B
Toph uses cookies. By continuing you agree to our Cookie Policy.