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
kavishrox:
2012-09-18 16:06:02
I think test cases are a bit weak .. such good problems shouldn't get so easily AC until the code is near to most optimized ..I wonder how my code ran within 0.1 sec . It should rather have been around 0.5 or so .. |
|
kavishrox:
2012-09-15 19:03:59
nice concept.. Until now I always did such questions wrong and they even got ac because no one cared for this silly mistake. :P Last edit: 2012-09-17 18:15:50 |
|
akb:
2012-08-30 14:53:07
Awesome Question Man... |
|
Bruno Adami:
2012-08-16 01:25:46
Hi, my acc results in:
|
|
Ankit Paharia:
2012-08-15 16:50:07
I am getting WA.... though my code works fine till 10^15....
|
|
:D:
2012-08-13 17:24:12
No, f(n) should remain intact when put it into g(n) formula. |
|
Will be back ;):
2012-08-13 15:20:25
Hint: a little knowledge might help.
|
|
devu:
2012-08-11 16:51:47
Nice Decission by Problem setter, :)
|
|
:D:
2012-08-11 12:35:12
Moved the previous version to tutorial. |
|
Francky:
2012-08-11 08:50:50
http://www.spoj.pl/problems/OPC3A/ already exists, I don't think this new version give a new challenge !
|
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 |