FLIB  Flibonakki
G(n) is defined as
G(n) = G(n1) + f(4n1) , 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
matcha1998:
20170911 14:33:45
Application of Matrix Exponentiation!!


l0gic_b0mb:
20170623 19:41:31
3x3 works if you reduce the MOD operations and don't overload the * operation to multiply matrices (or create a separate function to do the same). Dirty Optimisations. xP Last edit: 20170623 19:43:52 

candide:
20170429 20:14:59
G(n) depends on two consecutive Fibonacci numbers, so you only need to fastpower a 2x2 integer matrix (fastpower = squareandmultiply algorithm). In C, this can get AC in 0.02s without any trick (2017/05). To do a better result, perform precomputation (little tricky). Same advice in order to get AC in Python. Congrat to Francky for his Python performance! 

galang:
20160915 07:23:31
used 3x3 matrix with some precomputation, AC 0.10 s 

farhad chowdhury:
20160412 19:09:43
can anyone plz share the idea how it can be solved with a 2*2 matrix.


Tahsin:
20150724 11:21:46
3*3 matrix passed , but without overloading * operator :/ with overloading i got TLE : time limit is so strict ! 

#include:
20150304 13:41:34
2 WAs because of int in place of long long int 

ivar.raknahs:
20150303 16:00:16
reduce as much mod operation as you can.


Abhishek:
20141226 17:55:45
Remember , The Fib(n) can also be calculated in O(logn) , if you read CLRS in a proper manner , you can never miss this! 

Kriti Joshi:
20141210 08:31:26
After repeated TLEs , WAs and silly mistakes finally accepted :) Enjoyed solving it. 
Added by:  Prof_Utonium_ಉಮೆಶ್ 
Date:  20101005 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSRHINO OBJC SQLITE 
Resource:  MNNIT IOPC 2010 