FLIB - Flibonakki

no tags 

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

hide comments
restricteur: 2011-07-05 08:29:30

I've got an NZEC even if I put an infinite loop at the beginning of the main method. Normally I should see a TLE ??!!

EDIT: accepted after porting from JAVA to C++

This is not fair :(

Last edit: 2011-07-05 09:21:42
mukesh tiwari: 2011-06-24 13:09:53

2x2 matrix exponentiation in Haskell is TLE.

Santiago Zubieta: 2011-05-02 16:49:07

I'm getting TLE, I guess my solution is sort of archaic
I read a, I call gib(a) where gib(a) is a recursive function on itself and fib(a) (which is another recursion) :( hahaha

prp: 2011-02-02 13:40:57

its showing wrong answer but its running perfectly on my machine

sandeep pandey: 2010-12-24 16:36:11


phew!AC:-))

Last edit: 2011-03-06 11:54:40
David Gómez: 2010-12-19 23:31:33

block is right. But, with some optimizations you can get AC using 3*3 matrix exponentiation.

Last edit: 2010-12-20 00:04:16
Anoop Chaurasiya: 2010-11-07 19:29:04

time limit is too strict,merely using 3*3 matrix exponentiation instead of 2*2 gave me TLE

Last edit: 2010-11-07 19:29:53

Added by:Prof_Utonium_ಉಮೆಶ್
Date:2010-10-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-RHINO OBJC SQLITE
Resource:MNNIT IOPC 2010