## POWFIB - Fibo and non fibo

The problem is simple.

Find  (a^b) % MOD

where ,

a = Nth non-fibonacci number

b = (Nth fibonacci number)%MOD

MOD = 10^9+7

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

Note : It is guaranteed that Nth non-fibonacci number will always be less than MOD value for every value of N used.

### Input

First line contains T , the number of test cases
Each next T lines contains a  number N.

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.

Announcement: Constraints are updated. Sorry for inconvenience occurred.

### Example

`Input:`
```3
3
2
1```
`Output:`
```49
6
4
```
`Explanation`
`For N=3 : 3rd non fibo number =7, 3rd fibo number=2. ans= (7^2) %MOD =49`
`For N=2 : 2nd non fibo number =6, 2nd fibo number=1. ans=(6^1) %MOD=6`
`For N=1 : 1st non fibo number =4, 1st fibo number=1.  ans= (4^1) %MOD =4`
`Constraints`
`1<=T<=100000`
`1<=N<=9*10^8`
`Note: Test cases have been updated and costraints are changed.  Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.`

 < Previous 1 2 3 4 5 Next > prbhatter: 2021-04-14 06:33:20 @nimphy is correct I think.... "b" should be calculated under modulo (MOD-1) and not MOD. This link should explain why is it so -> https://www.geeksforgeeks.org/find-power-power-mod-prime/ If this is wrong, then please could someone explain why "b" should be computed under modulo MOD and not (MOD-1)? [NG]: There is nothing one "should" do here other than what the problem statement stipulates. Last edit: 2021-04-14 08:28:05 nimphy: 2018-05-17 02:33:45 when I get “b”，I should mod 1e9+7-1，right？ But I get WA； while mod 1e9+7 get AC。What is the problem~~~~ darkdreamofmy1: 2017-08-27 20:00:35 Wrong answer on test case 14 but why!! sak3t: 2017-01-02 15:06:28 I have got 3 WAs. I am sure my code is correct. :/ WA on 14th test. Everytime. -_- EDIT: Got it. Stupid mistake -_- Anyways I have got AC in 6.06 s. Is there any better approach, I used matrix exponentiation? Last edit: 2017-01-08 20:47:53 Ketan Chandak: 2016-07-29 17:19:18 O(T*log(n)) gives TLE with scanf/printf. Too tight Time Limit? Sarthak Munshi: 2016-06-05 09:21:23 @ivar.raknahs : can you please check my latest submission . Last edit: 2016-06-05 16:53:07 abhi_vicky: 2016-02-25 08:31:07 using matrix exponantion....AC in one go. shubham: 2016-01-14 13:25:05 Nice question!!! constraints are good. anil2496: 2016-01-11 19:11:47 learnt a lot priyank: 2015-12-15 19:49:01 finally solved with lowest time in java after more than 25 tle and wrong answer :)