设 \(G\) 为斐波那契数列的生成函数，显然有 \(F = F \times G + 1\)。那么 \(F = \frac{1}{1 - G} = 1 + \frac{x}{1 - 2x - x^2}\)。问题是如何展开 \(\frac{x}{1 - 2x - x^2}\)。
因为 \(\frac{1}{1 - ax} = \sum\limits_{i \ge 0} (ax)^i\)，所以考虑设 \(\frac{x}{1 - 2x - x^2} = \frac{A}{1 - ax} + \frac{B}{1 - bx} = \frac{A + B - (Ab + Ba)x}{1 - (a + b)x + abx^2}\)。对比系数后解得 \(A = \frac{\sqrt 2}{4}, B = -\frac{\sqrt 2}{4}, a = 1 + \sqrt{2}, b = 1 - \sqrt{2}\)。那么答案即为：
\[\frac{\sqrt 2}{4} ((1 + \sqrt 2)^n - (1 - \sqrt 2)^n) \]这样我们得到了求一个封闭形式的生成函数的某一次项的系数的通法。
code
// Problem: P4451 [国家集训队] 整数的lqp拆分
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4451
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 10050;
const ll mod = 1000000007, B = 59713600;
const ll inv4 = (mod + 1) / 4;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
char s[maxn];
void solve() {
scanf("%s", s);
ll n = 0;
for (int i = 0; s[i]; ++i) {
n = (n * 10 + s[i] - '0') % (mod - 1);
}
ll ans = qpow((1 + B) % mod, n);
ans = (ans - qpow((1 - B + mod) % mod, n) + mod) % mod;
ans = ans * B % mod * inv4 % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}