Shivam is a genious, as you all know..:P
Recently he discovered that every whole number in the universe can be represented as the sum of three numbers 1, 3 and 4.
He was so much fascinated by the fact, that he began to write every number as sum of these numbers.
Later he found that, there are multiple ways of decomposing a number into the sum of 1, 3, and 4.
For example:
5 = 1+1+1+1+1 = 1+1+3 = 1+3+1 = 3+1+1 = 1+4 = 4+1
Now he wants to know what are the total number of ways to represent a number as the sum of 1, 3 and 4.
Help him to calculate the total ways.
Since the number can be large, print it modulo 10^7+7.
Input Format:
Input will begin by T, the number of test cases.
Each of the next T lines contain a single integer n.

Output Format:
For each n, print a single integer,representing the number of ways to decompose n MOD 10^7+7.

Scoring Criteria:
20 Points: 1 ≤ T ≤ 10 n ≤ 15
40 Points: 1 ≤ T ≤ 100000 n ≤ 1000000

SAMPLE INPUT
2
5
7

SAMPLE OUTPUT
6
15

见题面

见题面