SP7487 FLIB - Flibonakki

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.

First line contains number of test cases t (t

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