G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is ith Fibonacci number. Given n you need to evaluate G(n) modulo 1000000007.

Input

First line contains number of test cases t (t<40000). Each of the next t lines contain an integer n ( 0 <= n < 2^51).

Output

For each test case print G(n) modulo 1000000007.

Example

Input:
2
2
4

Output:
15
714