#include #define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++) #define all(v) begin(v),end(v) using namespace std; using ll = long long; bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; } bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; } #include #include using namespace atcoder; typedef atcoder::modint998244353 mint; vector BerlekampMassey(const vector &s) { const int N = (int)s.size(); vector b, c; b.reserve(N + 1); c.reserve(N + 1); b.push_back(mint(1)); c.push_back(mint(1)); mint y = mint(1); for (int ed = 1; ed <= N; ed++) { int l = int(c.size()), m = int(b.size()); mint x = 0; for (int i = 0; i < l; i++) x += c[i] * s[ed - l + i]; b.emplace_back(mint(0)); m++; if (x == mint(0)) continue; mint freq = x / y; if (l < m) { auto tmp = c; c.insert(begin(c), m - l, mint(0)); for (int i = 0; i < m; i++) c[m - 1 - i] -= freq * b[m - 1 - i]; b = tmp; y = x; } else { for (int i = 0; i < m; i++) c[l - 1 - i] -= freq * b[m - 1 - i]; } } reverse(begin(c), end(c)); return c; } mint bostan_mori(ll n, vector p, vector q){ assert(p.size() < q.size()); while (n > 0){ vector qi((int)q.size()); for (int i=0; i<(int)q.size(); i++){ if (i%2==0) qi[i] = q[i]; else qi[i] = -q[i]; } vector qq = convolution(q, qi); q.resize(((int)qq.size()+1)/2); for (int i=0; i<((int)qq.size()+1)/2; i++){ q[i] = qq[2*i]; } vector pp = convolution(p, qi); if (n%2==0){ p.resize(((int)pp.size()+1)/2); for (int i=0; i<((int)pp.size()+1)/2; i++){ p[i] = pp[2*i]; } }else{ p.resize((int)pp.size()/2); for (int i=0; i<(int)pp.size()/2; i++){ p[i] = pp[2*i+1]; } } n/=2; } return p[0]*q[0].inv(); } int main(){ cin.tie(0)->sync_with_stdio(0); ll n, k; cin >> n >> k; vector f(300); f[1] = 1; rep(i,2,300){ f[i] = f[i-1] + f[i-2]; } rep(i,0,300){ f[i] = f[i].pow(k); } rep(i,1,300){ f[i] += f[i-1]; } vector g = BerlekampMassey(f); f = convolution(f,g); f.resize((int)g.size()-1); cout << bostan_mori(n,f,g).val() << '\n'; }