rahul-and-fibonacci-series

Rahul loves Fibonacci number . He has been given a question .

Find  :  (A^B) % M

where,

A =   Nth non-fibonacci number

B =   (Nth fibonacci number) % M

M=   10^9 + 7

Consider Fibonacci series as 1,1,2,3,....

Help Rahul to solve this question by writing code for him!

Note: It is guaranteed that Nth non-Fibonacci number will always be less than the value of M for every value of N used in the problem.

Input:

First line contains T , the number of test cases.

Each next T lines contains a  number N.

Output:

Print T lines of output where each line corresponds to the required answer. 

Constraints:

1 ≤ T ≤100000

1 ≤ N ≤9*10^8

SAMPLE INPUT
3
3
2
1

SAMPLE OUTPUT
49
6
4

Explanation

For N=3 : 3rd non fibo number =7, 3rd fibo number=2. ans= (7^2)%M=49

For N=2 : 2nd non fibo number =6, 2nd fibo number=1. ans=(6^1)%M=6

For N=1 : 1st non fibo number =4, 1st fibo number=1.  ans= (4^1)%M=4

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: