Flibonakki

Problem code: AVISKR02

All submissions for this problem are available.

Flibonakki series G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is our good old Fibonacci series. Given n you need to evaluate G(n).

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 the nth flibonakki number modulo 1000000007.

Example

Input:
2
2
4


Output:
15
714
Author: mandark
Date Added: 28-09-2010
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

triplem, Can I not submit my

zingoba @ 13 Oct 2010 07:45 PM

triplem, Can I not submit my solution to this problem?

I found the right place to

zingoba @ 13 Oct 2010 07:46 PM

I found the right place to submit solution using the URL.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions