Changu and Mangu are brothers. Changu likes 2 and Mangu likes 3. They decided to express each number as sum of 2 and 3.

They need your help. They want you to tell them the number of ways of writing a number as ordered sums of 2 and/or 3.

For example,  there are 4 ways to write 8 as an ordered sum of 2s and/or 3s:

 2 + 2 + 2 + 2

 2 + 3 + 3

3 + 2 + 3

3 + 3 + 2

Input

The first line contains T, the number of test cases. It is followed by T lines, each containg a number N.

Output

You have to print the number of ways of writing N as ordered sum of 2 and/or 3. You have to print the answer mod 1000000007.

Example

Input:

3

2

3

8

Output:

1

1

4

Constraints:

T<=100000

1<=N<=1000000