gaurav-and-cities

We all are aware of Gaurav and his love for "weird" recurrences.
Recently, he came up with another of his wierd recurrence namely the "12321" recurrence.
F(n)= 1 * F(n-1) + 2 * F(n-2) + 3 * F(n-3) + 2 * F(n-4) + 1 * F(n-5)
He intends to make the use of his new "weird" recurrence for his latest encryption technique. 
Rajat, an ethical hacker and a friend of Gaurav claimed that his encryption technique has loopholes and can be broken in no time.
To prove his claim, Rajat needs to find the Nth number of the sequence formed using the recursion as fast as possible.   

Using his knowledge of hacking, he was able to get some seed values of the recurrence that Gaurav intends to use in his encryption.
F(1)=1 
F(2)=2 
F(3)=3 
F(4)=2 
F(5)=1

Help Rajat hack Gaurav's recurrence by your programming skills. Your hack will decide the future of "Cryptography".
Input Format:
First line will contain T, the number of test cases.
Following T lines contain a single integer n.

Output Format: 
Output a single line for each test case, denoting the value of F(n)%(10000007).

Scoring Criteria:
20 Points: T ≤ 10 and 1 ≤ N ≤ 25
50 Points: T ≤ 1000 and 2 ≤ N ≤ 100000
90 Points: T ≤ 10000 and 2 ≤ N ≤ 10^(18)

SAMPLE INPUT
2
10
29

SAMPLE OUTPUT
524
8647330

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: