Luogu

分析

设 $g_n$ 为 $n$ 的答案，则
$$
g_n=\begin{cases}1,&n=0\\\sum_{i=0}^nF_i\times g_{n-i},&n\geq 1\end{cases}
$$
设 $F(x)$ 为 $F_i$ 的 OGF，$G(x)$ 为 $g_i$ 的 OGF，于是有
$$
G(x)=F(x)G(x)+1
$$
所以
$$
G(x)=\frac{1}{1-F(x)}
$$
我们知道
$$
F(x)=\frac{x}{1-x-x^2}
$$
所以
$$
\begin{aligned}
G(x)&=\frac{1-x-x^2}{1-2x-x^2}\\
&=1+\frac{x}{1-2x-x^2}\\
&=1+\frac{x}{[1-(1+\sqrt{2})x][1-(1-\sqrt{2})x]}\\
&=1+\frac{1}{2\sqrt{2}}\left[\frac{1}{1-(1+\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x}\right]\\
&=1+\sum_{i=0}^{+\infty}\frac{(1+\sqrt{2})^i-(1-\sqrt{2})^i}{2\sqrt{2}}x^i
\end{aligned}
$$
我们只需要求 $[x^n]G(x)$，即 $\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$，而 $2$ 在模 $10^9+7$ 意义下是有二次剩余的，所以直接计算即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int read() {
    int X=0; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=(10ll*X+c-'0')%(mod-1),c=getchar();
    return X;
}

int main() {
    int n=read();
    printf("%lld\n",14928400ll*(qpow(59713601,n)-qpow(940286408,n)+mod)%mod);
    return 0;
}