Problem #49
Hyper Sum of Fibonacci Numbers
Let F(n) be the n-th Fibonacci number. That is, F(n) satisfies
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)\ \ ({\rm if}\ n \ge 2).
Let f_k(n) be the function such that
f_0(n) = F(n),
f_k(n) = \sum\limits_{i=1}^n f_{k-1}(i)\ \ ({\rm if}\ k \ge 1).
You are given that f_1(1) = 1, f_2(2) = 3 and f_{10}(10) = 130965.
Find f_{10^8}(10^8) \pmod{1\ 000\ 000\ 007}.