POWFIB - Fibo and non fibo

The problem is simple - find (ab) % MOD, where:

  • a = Nth non-Fibonacci number.
  • b = (Nth Fibonacci number) % MOD.
  • MOD = 109+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.

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 Fibonacci number = 7, 3rd Fibonacci number = 2. answer = 72 % MOD = 49
  • For N=2 : 2nd non Fibonacci number = 6, 2nd Fibonacci number = 1. answer = 61 % MOD = 6
  • For N=1 : 1st non Fibonacci number = 4, 1st Fibonacci number = 1. answer = 41 % MOD = 4

Constraints

1 ≤ T ≤ 100000

1 ≤ N ≤ 9×108

Note: Test cases have been updated and constraints are changed. Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.


Added by:ivar.raknahs
Date:2015-07-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:OWN

hide comments
2016-01-11 19:11:47
learnt a lot
2015-12-15 19:49:01 priyank
finally solved with lowest time in java after more than 25 tle and wrong answer :)
2015-10-30 19:33:55
after 4 WA finally AC!!!!!


Last edit: 2015-10-30 19:34:36
2015-10-27 08:00:59
hurray! got accepted. :)
Feeling good

Last edit: 2015-10-27 08:01:28
2015-10-26 19:38:32
@author: please help why i am getting wrong answer after case 15. many WAs.
This is my code. <snip>
please help me :(
Tried all data types. Still could not figure it out.

Last edit: 2022-08-09 22:50:55
2015-10-26 14:29:29
i am getting WA after 12th test case @ivar.raknahs

Last edit: 2015-10-26 14:33:19
2015-10-23 08:33:16 Aditya Kumar
Wrong Data Type costed me couple of WA!!
2015-08-22 12:22:24
@ivar.raknahs : Can you plz check my submission ID-14951756. I already got more than 8 WA. Don't know where i m wrong.
2015-08-21 21:20:56
@ivar.raknahs I'm confused. The time limit is 1 second, but today answers taking 3 seconds were accepted.

-reply-> the time that judge gives you is the total time taken for all input file

Last edit: 2015-09-03 16:25:51
2015-08-17 13:28:58 Dune
@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.
(I've constated my submission of 2015-07-26 hasn't been rejudged)

Last edit: 2015-08-17 20:47:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.