SPOJ.com - Problem FLIB

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

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	Francky: 2012-12-31 01:27:53 I was waiting for that moment since almost a year !!! It's feasible in Python !!! My code has 888 Bytes, do a small precomp part, then for each n compute flib(n) with only 6 mul(32+32=64bits) and 4 mod operations (and few other small ops). My IO are not magic, so it can be much faster.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-12-30 15:59:08 -My first submission 8 months ago is using 5x5 matrix and got AC in 0.84s -Now I try with 3x3 matrix and got AC again in 0.36s -Then I try again with 2x2 matrix and AC again in 0.26s -Next step, I reduce modulo operation and AC again in 0.16s -After that, I use small precomputation and AC in 0.12s -Finally fixing my fast I/O and submit again, AC in 0.11s Nice problem, found so many trick for optimization.. and my best is 0.11s, I still curious how to get accepted in ~0.03s...
	StupidGuy: 2012-09-13 20:23:05 What is ans for 2^51-1 ? ------------------------- EDIT: AC. val for 2^51-1 is 847805763 Very tough to get AC in java Last edit: 2012-09-14 22:28:34
	god_father: 2012-08-10 20:31:32 do not use unnecessary modulo it cost me 2 times TLE...
	Prakhar Jain: 2011-12-23 18:01:55 what's the problem here....even 22 matrix with log(n) solution is exceeding time limit........:( Last edit: 2011-12-23 19:34:38*
	manu: 2011-12-04 13:16:20 Ahh... Done finally!! :)
	Gurpreet Singh: 2011-10-01 19:16:24 '0' is not in the input file. My code which stops working if input = 0 , got AC.
	bashrc is back: 2011-09-27 16:33:50 2*2 without any optimization....(even with redundancy) gave me AC Time limit is fair...Just use pen and paper for expanding the series...
	darryl: 2011-07-12 10:05:11 fun problem. enjoyed solving it
	Kunal: 2011-07-07 22:32:37 Can some one provide some big test cases with correct answers . Thanks in advance.

Submit solution!

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