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
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..
|
|
[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 ;-)
|
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 |