Mr. 10-pointer and Mr. Gyani had been trying to count the number of ways to perfectly cover a 1-by-n board with monominoes and dominoes.

With pen-and-pencil they are only able calculate the count for small n.
For example:
1-by-1 = 1 (only one monomino)
1-by-2 = 2 (either use two monomino or one domino)
1-by-3 = 3 (either all monomino, or 1 monomino followed by a domino, or 1 domino followed by a monomino).

So they approached Ms. Pavani to help them calculate the same for large n. Help her to code the solution which print the total number of ways modulo (10⁸ + 7).

Input

The first line of the input contains number of test cases, T. Then follows T lines containing a number n, size of baord.

Output

For each test case print the number of ways to cover a 1-by-n board modulo (10⁸ + 7).

Constraints:

a) 0 < T ≤ 10³

b) 0 < n ≤ 10⁶

Example

Input:
4
1
2
3
500

Output:
1
2
3
12577845

Note:

a) Perfect cover means the whole board should be completely covered, no two monomino/domino overlap each other, neither any of them lie outside of the boundary of board.

b) Monomino is of block size 1-by-1, and orientation of the monomino is not to be considered.

c) Size of a domino is 1-by-2.