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