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
matcha1998: 2017-09-11 14:33:45

Application of Matrix Exponentiation!!
AC in one GO!!

l0gic_b0mb: 2017-06-23 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: 2017-06-23 19:43:52
candide: 2017-04-29 20:14:59

G(n) depends on two consecutive Fibonacci numbers, so you only need to fast-power a 2x2 integer matrix (fast-power = square-and-multiply 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: 2016-09-15 07:23:31

used 3x3 matrix with some precomputation, AC 0.10 s

farhad chowdhury: 2016-04-12 19:09:43

can anyone plz share the idea how it can be solved with a 2*2 matrix.
i know with 3*3 matrix but tons of tle also did a lot optimization

Tahsin: 2015-07-24 11:21:46

3*3 matrix passed , but without overloading * operator :/ with overloading i got TLE :| time limit is so strict !

#include: 2015-03-04 13:41:34

2 WAs because of int in place of long long int

ivar.raknahs: 2015-03-03 16:00:16

reduce as much mod operation as you can.
long long is good but too much mod operation can TLE.
AC .

Last edit: 2015-03-03 16:00:39
Abhishek: 2014-12-26 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: 2014-12-10 08:31:26

After repeated TLEs , WAs and silly mistakes finally accepted :) Enjoyed solving it.


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