Jhumru, the monkey is very fond of climbing the poles. After practicing, now he can jump either 1 unit or 2 units or 3 units at a time. Therefore, he thought that there are many possible ways to climb the pole of the same height. For example, if he wants to climb a pole of height 2 units, he might climb 2 units directly or he may climb 1 unit two times to reach the top of the pole, but he cannot jump to 3 units because height of pole is 2. Now, he wonders how many ways are possible to climb a pole of height H.

Since he is a monkey, he doesn't know programming. So, he asks you to find the number of ways in which he can climb the pole of height H by using only one of his 3 jumps. Since, the number of ways can be very large, output the result mod 10^8 + 7.

Input

First line of Input contains a single number T(<= 10,000), the number of Test Cases

Next T lines contains H(1 <= H <= 10^18), the height of the pole

Output

T lines each containing the number of ways in which Jhumru can climb the pole. Since the number can be very large output the number mod 10^8 + 7.

Example

Input:
3

1

2

5

Output:
1

2

11

Explanation:

For H = 1, the only possible way is to climb 1 unit.

For H = 2, he may directly climb 2 units in single step or he may climb 2 times with a height of 1 unit each.