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

10 = 766762396
10^15 = 501491213
235869845625 = 546004542

Ankit Paharia: 2012-08-15 16:50:07

I am getting WA.... though my code works fine till 10^15....
10 - 766762396
10^15 - 4331549
235869845625 - 322446325
please chk whether they are correct ???

: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.

Last edit: 2012-08-23 13:27:49
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 !
Edit : OK now, OPC3A is in tutorial.

Last edit: 2012-08-11 13:09:56

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