---

Problem 739

---

Summation of Summations

Take a sequence of length $n$. Discard the first term then make a sequence of the partial summations. Continue to do this over and over until we are left with a single term. We define this to be $f(n)$.

Consider the example where we start with a sequence of length $8$:

$$\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}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}$$

Then the final number is $429$, so $f(8)=429$.

For this problem we start with the sequence $1,3,4,7,11,18,29,47,\dots$
This is the Lucas sequence where two terms are added to get the next term.
Applying the same process as above we get $f(8)=2663$.
You are also given $f(20)\equiv 742296999mod1000000007$.

Find $f({10}^8)$. Give your answer modulo $1000000007$.

---

求和再求和

考虑一个长度为$n$的数列，先去掉第一项并求部分和，再对部分和序列不断重复同样的操作，直到只剩下一项。我们记剩下的这一项为$f(n)$。

如下展示的例子中，初始序列为$8$个$1$：

$$\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}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)\equiv 742296999mod1000000007$。

求$f({10}^8)$，并将你的答案对$1000000007$取余。

---