739 : 和の和

長さ$n$の数列を取り上げる。初項を取り除いた列の部分和の列を作る。最終的に1項だけ残るまでこれを繰り返す。この値を$f(n)$とする。

長さ8の数列から開始した、以下の例を考える。

$\begin{array}{rrrrrrrr}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ & & 2 & 5 & 9 & 14 & 20& 27 \\ & & & 5 & 14 & 28 & 48 & 75 \\ & & & & 14 & 42 & 90 & 165 \\ & & & & & 42 & 132 & 297 \\ & & & & & & 132 & 429 \\ & & & & & & & 429 \end{array}$

最後の数は 429 なので、$f(8) = 429$である。

ここで$1, 3, 4, 7, 11, 18, 29, 47, \dots$で始まる数列を考える。 この数列はリュカ数列であり、2項の和が次の項になる。 上と同じ過程を踏むと$f(8) = 2663$になる。 また$f(20)=742296999 \mod 1\,000\,000\,007$である。

$f(10^8)$を求め、$1\,000\,000\,007$で割った剰余を答えよ。