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

First line contains T , the number of test cases

Print T lines of output where each line corresponds to the required answer. **Announcement:** Constraints are updated. Sorry for inconvenience occurred.