In the University College of JNTUK Vizianagaram external lab examinations were being conducted. Management has decided to strictly prohibit the mal practices for that the management has decided to arrange cardboards of size nx2 to place in between two successive systems.
The construction of cardboard can be done only by using cardboard (Single cardboard) of size 1x2 (either dimensions).Write a program that takes input N and outputs the number of different ways construction of required cardboard can be done. Output the answer mod 10^9 +7

Input
First line contains T (number of test cases)
Next T lines contain N.

Output
T lines with desired answer mod 1000000007 in each line.

Constraints

1<=T<=1000
1<=N<=10^6

Example
Input:
3
1
2
3

Output:
1
2
3

见题面

见题面