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(n1)for n>0
g(0)=1for n==0
f(n) denotes the nth fibonacci number where
f(0)=1
f(1)=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(n)=f(n1)+f(n2)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
Output :
The value of g(n)%(10^9+7)
Warning: value of n won't fit in int,use long long int instead
Sample Cases : Input: 2 3 5 Output: 4 32
hide comments
:.Mohib.::
20150722 11:45:05
Awsm que...Learned very important concept..... :) 

hamza007:
20140723 21:36:20
what an awesome mathematical question !! 

Francis:
20140415 15:51:25
AC with one try using eulerv totient function~nice prob :) 

Vijay Jain:
20130714 07:43:30
very tight time limit..


[Lakshman]:
20130507 15:48:08
getting TLE...using Java same algo get ac in C++; how people get AC using java...? Last edit: 20130507 16:03:13 

niraj kant sinha:
20130228 23:24:26
very easy if you know some number theory :) 

Aditya Pande:
20121218 08:33:01
really good problem 

Francky:
20120918 16:17:59
@kavish dwivedi : do it in Python, and come back after that ;)

Added by:  bashrc is back 
Date:  20120810 
Time limit:  0.163s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 