Limits 1s, 512 MB

Anuska, A pretty girl lives in a country named nebula. She is amazing to see. For this reason her parents never let her go outside alone. Yesterday, her parents left home for important works for few days leaving her alone in home. She thinks this is the only chance she can travel her country. She took the map of the country roads. She was confused while looking for a suitable place to travel because of nebula’s strange structure.

Nebula is a strange country. Every city is connected with only 2 next cities. Suppose, Nebula has N cities where city No 1 is connected with city no 2 and city no 3. City no 2 is connected with city No 3 and city No 4. So, Anuska can go to city no 3 from 1 in two ways. One is 1-2-3 and another is 1-3. She tried to calculate how many ways she can travel to a city. Her home town was city no 1.

As she is pretty, she is disinterested in study. She wants your help. Helps the pretty girl and get a chance to end your single life.

Input

First line will contain a positive number T(1<=T<= 1000). T denotes the number of test cases.
Next T Lines will contain an integer number N (1 <= N<= 1000000). N denotes the city number she wants to travel.

Output

Only line per test cases that will contain number of ways to travel the city. As the answer can be very large print it modulo 1000000007.

Sample

InputOutput
3
2
3
1
1
2
1

Submit

Login to submit.

Statistics

65% Solution Ratio
codebreaks007Earliest, Apr '18
steinumFastest, 0.0s
steinumLightest, 9.3 kB
steinumShortest, 333B
Toph uses cookies. By continuing you agree to our Cookie Policy.