MNNITAR - Arya Rage

Arya is very fond of Fibonacci numbers. He claimed he can solve any problem on Fibonacci number. His clever friend Golu gave him a challenge to prove his skills. He gave him a sequence which he called exponacci. The sequence is given by

  • g(n) = 2^f(n-1) for n > 0
  • g(0) = 1 for n == 0

f(n) denotes the nth Fibonacci number where

  • f(0) = 1 (Obviously Golu is not as good as Arya in Fibonacci numbers so he believes f(0) = 1, anyways we have chosen not to disturb him.)
  • f(1) = 1
  • f(n) = f(n-1) + f(n-2) for n > 1

Help Arya to find the nth exponacci number. Since the numbers can be very large take mod 10^9+7.

Input

The first line of the input will be the number of test cases (T <= 2000). For each test case first line contains one integers n (0 <= n <= 10^15)

Warning: value of n won't fit in int, use long long int instead.

Output

The value of g(n) % (10^9+7)

Sample

Input:
2
3
5

Output:
4
32

Added by:bashrc is back
Date:2012-08-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-07-22 11:45:05 :.Mohib.:
Awsm que...Learned very important concept..... :)
2014-07-23 21:36:20 hamza007
what an awesome mathematical question !!
2014-04-15 15:51:25 Francis
AC with one try using eulerv totient function~nice prob :)
2013-07-14 07:43:30 Vijay Jain
very tight time limit..
i use correct algo... just use matrix made of vector and got tle for 4 times..
2013-05-07 15:48:08 [Lakshman]
getting TLE...using Java same algo get ac in C++; how people get AC using java...?

Last edit: 2013-05-07 16:03:13
2013-02-28 23:24:26 niraj kant sinha
very easy if you know some number theory :)
2012-12-18 08:33:01 Aditya Pande
really good problem
2012-09-18 16:17:59 Francky
@kavish dwivedi : do it in Python, and come back after that ;-)
Constraints are very good. It's hard to do it in 0.00s in fast language, it's a very good challenge.
If you want a harder problem, go to FLIB.

Last edit: 2012-09-18 16:19:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.