取一个长度为$n$的序列。丢弃第一项，然后进行一系列部分求和。继续一遍又一遍地这样做，直到我们只剩下一个术语。我们将其定义为$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$
这是卢卡斯序列，其中两项相加得到下一项。
应用与上面相同的过程，我们得到 $f(8)=2663$。
您还得到 $f(20)=742296999$ 模 $1000000007$

求$f({10}^8)$。以 $1000000007$ 为模给出你的答案。