POWFIB - Fibo and non fibo
The problem is simple.
Find (a^b) % MOD
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.
Each next T lines contains a number N.
Print T lines of output where each line corresponds to the required answer.
Announcement: Constraints are updated. Sorry for inconvenience occurred.
3 3 2 1
49 6 4
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
Note: Test cases have been updated and costraints are changed. Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.
finally solved with lowest time in java after more than 25 tle and wrong answer :)
after 4 WA finally AC!!!!!
hurray! got accepted. :)
@author: please help why i am getting wrong answer after case 15. many WAs.
i am getting WA after 12th test case @ivar.raknahsLast edit: 2015-10-26 14:33:19
Wrong Data Type costed me couple of WA!!
@ivar.raknahs : Can you plz check my submission ID-14951756. I already got more than 8 WA. Don't know where i m wrong.
@ivar.raknahs I'm confused. The time limit is 1 second, but today answers taking 3 seconds were accepted.
@ivar.raknahs : testcases have been updated with cases where N>10^7, but previous submissions haven't been rejudged, you'll have to rejudge it.
@ivar.raknahs : Can you plz check my submission I think my algo is correct :(