PWSUMF - Fibonacci Power Sum

no tags 

Some people may found FIBOSUM a too easy problem. We propose here some serious constraints.

SigmaFibPw

Fib is the Fibonacci sequence:
For any positive integer i: if i<2 Fib(i) = i, else Fib(i) = Fib(i-1) + Fib(i-2)

Input

The input contains several lines, you don't have to process all, it may be hard, only all first ones you are able to, in the given time. Each line contains one integer : N.

Output

For the kth line, print Sum(Fib(i)^k for i in [1..N]).
As the answer could not fit in a 64-bit container, just output your answer modulo 1000000007.
The difficulty should increase as you will process lines.

Example

Input:
6
6
6
[...] some more lines
Output:
20
104
674
[...] as many as you can.

Explanations

For the first line : 1^1 + 1^1 + 2^1 + 3^1 + 5^1 + 8^1 = 20.
For the second line : 1^2 + 1^2 + 2^2 + 3^2 + 5^2 + 8^2 = 104
For the third line : 1^3 + 1^3 + 2^3 + 3^3 + 5^3 + 8^3 = 674.

Constraints

0 < N <= 10^9

The numbers N are uniform randomly chosen.
The challenge is to be the fastest. There were 30000 lines at time of publication.
Robert Gerbicz agreed to extend to 100000 lines using his fast C code. Congratulations again to him as a fabulous solver.
Now you have one point for the kth line. Constraints allow everybody to get some points.
If a much faster method is discovered, judge would take time into account.
For your information, my (our) method have an amortized complexity of O(k) for the kth line. Have fun ;-)



Added by:Francky
Date:2014-04-05
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem