## PWSUMF - Fibonacci Power Sum

no tags

Some people may found FIBOSUM a too easy problem. We propose here some serious constraints. 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