MNNITAR - Arya Rage

no tags 

 

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)=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(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

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.:: 2015-07-22 11:45:05

Awsm que...Learned very important concept..... :)

hamza007: 2014-07-23 21:36:20

what an awesome mathematical question !!

Francis: 2014-04-15 15:51:25

AC with one try using eulerv totient function~nice prob :)

Vijay Jain: 2013-07-14 07:43:30

very tight time limit..
i use correct algo... just use matrix made of vector and got tle for 4 times..

[Lakshman]: 2013-05-07 15:48:08

getting TLE...using Java same algo get ac in C++; how people get AC using java...?

Last edit: 2013-05-07 16:03:13
niraj kant sinha: 2013-02-28 23:24:26

very easy if you know some number theory :)

Aditya Pande: 2012-12-18 08:33:01

really good problem

Francky: 2012-09-18 16:17:59

@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

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