/* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //*/ #include <atcoder/all> // #include <atcoder/segtree> #include <bits/stdc++.h> using namespace std; using namespace atcoder; // #define _GLIBCXX_DEBUG #define DEBUG(x) cerr << #x << ": " << x << endl; #define DEBUG_VEC(v) \ cerr << #v << ":"; \ for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \ cerr << " " << v[iiiiiiii]; \ cerr << endl; #define DEBUG_MAT(v) \ cerr << #v << endl; \ for (int iv = 0; iv < v.size(); iv++) { \ for (int jv = 0; jv < v[iv].size(); jv++) { \ cerr << v[iv][jv] << " "; \ } \ cerr << endl; \ } typedef long long ll; // #define int ll #define vi vector<int> #define vl vector<ll> #define vii vector<vector<int>> #define vll vector<vector<ll>> #define pii pair<int, int> #define pis pair<int, string> #define psi pair<string, int> #define pll pair<ll, ll> template <class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); } template <class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); } template <class S, class T> ostream &operator<<(ostream &os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; } #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep1(i, n) for (int i = 1; i <= (int)(n); i++) #define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define rrep1(i, n) for (int i = (int)(n); i > 0; i--) #define REP(i, a, b) for (int i = a; i < b; i++) #define in(x, a, b) (a <= x && x < b) #define all(c) c.begin(), c.end() void YES(bool t = true) { cout << (t ? "YES" : "NO") << endl; } void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; } void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; } void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; } void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; } void no(bool t = true) { cout << (t ? "no" : "yes") << endl; } template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; } template <class T, class U> T ceil_div(T a, U b) { return (a + b - 1) / b; } template <class T> T safe_mul(T a, T b) { if (a == 0 || b == 0) return 0; if (numeric_limits<T>::max() / a < b) return numeric_limits<T>::max(); return a * b; } #define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end()); const ll inf = 1000000001; const ll INF = (ll)1e18 + 1; const long double pi = 3.1415926535897932384626433832795028841971L; int popcount(ll t) { return __builtin_popcountll(t); } vector<int> gen_perm(int n) { vector<int> ret(n); iota(all(ret), 0); return ret; } // int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; vi dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0}; vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1}; struct Setup_io { Setup_io() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(25); cerr << fixed << setprecision(25); } } setup_io; // constexpr ll MOD = 1000000007; constexpr ll MOD = 998244353; // #define mp make_pair #include <bits/stdc++.h> using namespace std; // https://web.archive.org/web/20220903140644/https://opt-cp.com/fps-fast-algorithms/ using mint = modint998244353; template <typename T> struct Factorial { int MAX; vector<T> fac, finv; Factorial(int m = 0) : MAX(m), fac(m + 1, 1), finv(m + 1, 1) { for (int i = 2; i < MAX + 1; i++) { fac[i] = fac[i - 1] * i; } finv[MAX] /= fac[MAX]; for (int i = MAX; i >= 3; i--) { finv[i - 1] = finv[i] * i; } } T binom(int n, int k) { if (k < 0 || n < k) return 0; return fac[n] * finv[k] * finv[n - k]; } T perm(int n, int k) { if (k < 0 || n < k) return 0; return fac[n] * finv[n - k]; } }; Factorial<mint> fc; template <class T> struct FormalPowerSeries : vector<T> { using vector<T>::vector; using vector<T>::operator=; using F = FormalPowerSeries; F operator-() const { F res(*this); for (auto &e : res) e = -e; return res; } F &operator*=(const T &g) { for (auto &e : *this) e *= g; return *this; } F &operator/=(const T &g) { assert(g != T(0)); *this *= g.inv(); return *this; } F &operator+=(const F &g) { int n = this->size(), m = g.size(); this->resize(max(n, m), T(0)); rep(i, m)(*this)[i] += g[i]; return *this; } F &operator-=(const F &g) { int n = this->size(), m = g.size(); rep(i, min(n, m))(*this)[i] -= g[i]; return *this; } F &operator<<=(const int d) { int n = this->size(); if (d >= n) *this = F(n); this->insert(this->begin(), d, 0); this->resize(n); return *this; } F &operator>>=(const int d) { int n = this->size(); this->erase(this->begin(), this->begin() + min(n, d)); this->resize(n); return *this; } F operator*(const T &g) const { return F(*this) *= g; } F operator/(const T &g) const { return F(*this) /= g; } F operator+(const F &g) const { return F(*this) += g; } F operator-(const F &g) const { return F(*this) -= g; } F operator<<(const int d) const { return F(*this) <<= d; } F operator>>(const int d) const { return F(*this) >>= d; } F pre(int sz) const { return F(begin(*this), begin(*this) + min((int)this->size(), sz)); } F rev() const { F ret(*this); reverse(begin(ret), end(ret)); return ret; } void shrink() { while (this->size() && this->back() == T(0)) { this->pop_back(); } } // O(n log n) F inv(int d = -1) const { int n = this->size(); assert(n != 0 && (*this)[0] != 0); if (d == -1) d = n; assert(d >= 0); F res{(*this)[0].inv()}; for (int m = 1; m < d; m *= 2) { F f(this->begin(), this->begin() + min(n, 2 * m)); F g(res); f.resize(2 * m), internal::butterfly(f); g.resize(2 * m), internal::butterfly(g); rep(i, 2 * m) f[i] *= g[i]; internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(2 * m), internal::butterfly(f); rep(i, 2 * m) f[i] *= g[i]; internal::butterfly_inv(f); T iz = T(2 * m).inv(); iz *= -iz; rep(i, m) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); } res.resize(d); return res; } // fast: FMT-friendly modulus only // O(n log n) F &multiply_inplace(const F &g, int d = -1) { int n = this->size(); if (d == -1) d = n + g.size() - 1; assert(d >= 0); *this = convolution(std::move(*this), g); this->resize(d); return *this; } F multiply(const F &g, const int d = -1) const { return F(*this).multiply_inplace(g, d); } // O(n log n) F ÷_inplace(const F &g, int d = -1) { int n = this->size(); if (d == -1) d = n; assert(d >= 0); *this = convolution(move(*this), g.inv(d)); this->resize(d); return *this; } F divide(const F &g, const int d = -1) const { return F(*this).divide_inplace(g, d); } F divide_polynomial_inplace(F g) { // https://qiita.com/hotman78/items/f0e6d2265badd84d429a#4%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE%E5%95%86%E4%BD%99%E3%82%8A // 実装は Nyaan さんのものをほぼコピーしている if (this->size() < g.size()) { this->clear(); return *this; } int n = (int)this->size() - (int)g.size() + 1; if ((int)g.size() <= 64) { // g が小さい時は愚直の方が早い F f(*this); g.shrink(); mint coeff = g.back().inv(); for (auto &x : g) x *= coeff; int deg = (int)f.size() - (int)g.size() + 1; int gs = g.size(); F quo(deg); for (int i = deg - 1; i >= 0; i--) { quo[i] = f[i + gs - 1]; for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j]; } *this = quo * coeff; this->resize(n, T(0)); return *this; } // rev が x に x^-1 を代入する行為とほぼ等しい return *this = ((*this).rev().pre(n).multiply(g.rev().inv(n))).pre(n).rev(); } F divide_polynomial(const F &g) const { // 高校で習うような多項式の割り算という意味での divide return F(*this).divide_polynomial_inplace(g); } F remainder_polynomial(const F &g) const { // 高校で習うような多項式の割り算という意味での remainder auto p = this->divide_polynomial(g); auto q = *this - p.multiply(g); q.shrink(); return q; } // sparse // O(nk) F &multiply_inplace(vector<pair<int, T>> g) { int n = this->size(); auto [d, c] = g.front(); if (d == 0) g.erase(g.begin()); else c = 0; for (int i = n - 1; i >= 0; i--) { mint ori = (*this)[i]; (*this)[i] *= c; for (auto &[j, b] : g) { while (this->size() <= i + j) this->push_back(0); (*this)[i + j] += ori * b; } } return *this; } F multiply(const vector<pair<int, T>> &g) const { return F(*this).multiply_inplace(g); } // O(nk) F ÷_inplace(vector<pair<int, T>> g) { int n = this->size(); auto [d, c] = g.front(); assert(d == 0 && c != T(0)); T ic = c.inv(); g.erase(g.begin()); rep(i, n) { for (auto &[j, b] : g) { if (j > i) break; (*this)[i] -= (*this)[i - j] * b; } (*this)[i] *= ic; } return *this; } F divide(const vector<pair<int, T>> &g) const { return F(*this).divide_inplace(g); } // multiply and divide (1 + cz^d) // O(n) void multiply_inplace(const int d, const T c) { int n = this->size(); if (c == T(1)) for (int i = n - d - 1; i >= 0; i--) (*this)[i + d] += (*this)[i]; else if (c == T(-1)) for (int i = n - d - 1; i >= 0; i--) (*this)[i + d] -= (*this)[i]; else for (int i = n - d - 1; i >= 0; i--) (*this)[i + d] += (*this)[i] * c; } // O(n) void divide_inplace(const int d, const T c) { int n = this->size(); if (c == T(1)) rep(i, n - d)(*this)[i + d] -= (*this)[i]; else if (c == T(-1)) rep(i, n - d)(*this)[i + d] += (*this)[i]; else rep(i, n - d)(*this)[i + d] -= (*this)[i] * c; } // O(n) T eval(const T &a) const { T x(1), res(0); for (auto e : *this) res += e * x, x *= a; return res; } // O(n) F &integral_inplace() { int n = this->size(); assert(n > 0); if (n == 1) return *this = F{0}; this->insert(this->begin(), 0); this->pop_back(); vector<T> inv(n); inv[1] = 1; int p = T::mod(); for (int i = 2; i < n; i++) { inv[i] = -inv[p % i] * (p / i); } for (int i = 2; i < n; i++) { (*this)[i] *= inv[i]; } return *this; } F integral() const { return F(*this).integral_inplace(); } // O(n) F &derivative_inplace() { int n = this->size(); assert(n > 0); for (int i = 2; i < n; i++) { (*this)[i] *= i; } this->erase(this->begin()); this->push_back(0); return *this; } F derivative() const { return F(*this).derivative_inplace(); } // O(n log n) F &log_inplace(int d = -1) { int n = this->size(); assert(n > 0 && (*this)[0] == 1); if (d == -1) d = n; assert(d >= 0); if (d < n) this->resize(d); F f_inv = this->inv(); this->derivative_inplace(); this->multiply_inplace(f_inv); this->integral_inplace(); return *this; } F log(const int d = -1) const { return F(*this).log_inplace(d); } // O(n log n) // https://arxiv.org/abs/1301.5804 (Figure 1, right) F &exp_inplace(int d = -1) { int n = this->size(); assert(n > 0 && (*this)[0] == 0); if (d == -1) d = n; assert(d >= 0); F g{1}, g_fft{1, 1}; (*this)[0] = 1; this->resize(d); F h_drv(this->derivative()); for (int m = 2; m < d; m *= 2) { // prepare F f_fft(this->begin(), this->begin() + m); f_fft.resize(2 * m), internal::butterfly(f_fft); // Step 2.a' { F _g(m); rep(i, m) _g[i] = f_fft[i] * g_fft[i]; internal::butterfly_inv(_g); _g.erase(_g.begin(), _g.begin() + m / 2); _g.resize(m), internal::butterfly(_g); rep(i, m) _g[i] *= g_fft[i]; internal::butterfly_inv(_g); _g.resize(m / 2); _g /= T(-m) * m; g.insert(g.end(), _g.begin(), _g.begin() + m / 2); } // Step 2.b'--d' F t(this->begin(), this->begin() + m); t.derivative_inplace(); { // Step 2.b' F r{h_drv.begin(), h_drv.begin() + m - 1}; // Step 2.c' r.resize(m); internal::butterfly(r); rep(i, m) r[i] *= f_fft[i]; internal::butterfly_inv(r); r /= -m; // Step 2.d' t += r; t.insert(t.begin(), t.back()); t.pop_back(); } // Step 2.e' if (2 * m < d) { t.resize(2 * m); internal::butterfly(t); g_fft = g; g_fft.resize(2 * m); internal::butterfly(g_fft); rep(i, 2 * m) t[i] *= g_fft[i]; internal::butterfly_inv(t); t.resize(m); t /= 2 * m; } else { // この場合分けをしても数パーセントしか速くならない F g1(g.begin() + m / 2, g.end()); F s1(t.begin() + m / 2, t.end()); t.resize(m / 2); g1.resize(m), internal::butterfly(g1); t.resize(m), internal::butterfly(t); s1.resize(m), internal::butterfly(s1); rep(i, m) s1[i] = g_fft[i] * s1[i] + g1[i] * t[i]; rep(i, m) t[i] *= g_fft[i]; internal::butterfly_inv(t); internal::butterfly_inv(s1); rep(i, m / 2) t[i + m / 2] += s1[i]; t /= m; } // Step 2.f' F v(this->begin() + m, this->begin() + min<int>(d, 2 * m)); v.resize(m); t.insert(t.begin(), m - 1, 0); t.push_back(0); t.integral_inplace(); rep(i, m) v[i] -= t[m + i]; // Step 2.g' v.resize(2 * m); internal::butterfly(v); rep(i, 2 * m) v[i] *= f_fft[i]; internal::butterfly_inv(v); v.resize(m); v /= 2 * m; // Step 2.h' rep(i, min(d - m, m))(*this)[m + i] = v[i]; } return *this; } F exp(const int d = -1) const { return F(*this).exp_inplace(d); } // O(n log n) F &pow_inplace(const ll k, int d = -1) { int n = this->size(); if (d == -1) d = n; assert(d >= 0 && k >= 0); if (d == 0) return *this = F(0); if (k == 0) { *this = F(d); (*this)[0] = 1; return *this; } int l = 0; while (l < n && (*this)[l] == 0) ++l; if (l == n || l > (d - 1) / k) return *this = F(d); T c{(*this)[l]}; this->erase(this->begin(), this->begin() + l); *this /= c; this->log_inplace(d - l * k); *this *= k; this->exp_inplace(); *this *= c.pow(k); this->insert(this->begin(), l * k, 0); return *this; } F pow(const ll k, const int d = -1) const { return F(*this).pow_inplace(k, d); } // O(n log n) F &shift_inplace(const T c) { int n = this->size(); fc = Factorial<T>(n); rep(i, n)(*this)[i] *= fc.fac[i]; reverse(this->begin(), this->end()); F g(n); T cp = 1; rep(i, n) g[i] = cp * fc.finv[i], cp *= c; this->multiply_inplace(g, n); reverse(this->begin(), this->end()); rep(i, n)(*this)[i] *= fc.finv[i]; return *this; } F shift(const T c) const { return F(*this).shift_inplace(c); } vector<T> multipoint_evaluate(vector<T> const &xs) const { // xs の各要素に対しての f(xs) を返す // https://rsk0315.hatenablog.com/entry/2020/04/05/190941#fn-ab0dfd97 // verify: https://judge.yosupo.jp/submission/220213 int m = xs.size(); // m 以上の最小の 2 べき int m2 = 1; while (m2 < m) { m2 <<= 1; } // セグ木のように (x - xs[i]) の積を構築する vector<F> g(m2 + m2, {1}); for (int i = 0; i < m; ++i) { g[m2 + i] = {-xs[i], 1}; // (x - xi) } for (int i = m2 - 1; i > 0; i--) { g[i] = g[i << 1 | 0].multiply(g[i << 1 | 1]); } // g[1] (根) を this を g[1] で割った余りにする // g[i] は親を g[i] で割った余りにする // 最終的に g[m2 + i] は f を (x - xs[i]) で割った余りになり、剰余の定理よりそれが求める答えとなる g[1] = this->remainder_polynomial(g[1]); for (int i = 2; i < m2 + m; i++) { g[i] = g[i >> 1].remainder_polynomial(g[i]); } std::vector<T> ys(m); for (int i = 0; i < m; i++) { ys[i] = g[m2 + i][0]; } return ys; } static F multiply_sequence(const vector<F> &fs) { if (fs.size() == 0) { return {1}; } // fs を全て掛け合わせる queue<F> qu; for (const auto &f : fs) { qu.push(f); } while (qu.size() > 1) { F f1 = qu.front(); qu.pop(); F f2 = qu.front(); qu.pop(); qu.push(f1.multiply(f2, f1.size() + f2.size() - 1)); } return qu.front(); } }; using fps = FormalPowerSeries<mint>; fps interpolate(const vector<mint> &xs, const vector<mint> &ys) { // https://rsk0315.hatenablog.com/entry/2020/04/05/203210 // https://ferin-tech.hatenablog.com/entry/2019/08/11/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E8%A3%9C%E9%96%93 も参考になる // n 次多項式 y = f(x) において、n + 1 個の点 (x_i, y_i) が与えられたとき、 // 係数 a_0, a_1, ..., a_n を求める int n = xs.size(); // n 以上の最小の 2 べき int n2 = 1; while (n2 < n) { n2 <<= 1; } // セグ木のように (x - xs[i]) の積を構築する vector<fps> mul(n2 + n2, {1}); for (int i = 0; i < n; ++i) { mul[n2 + i] = {-xs[i], 1}; // (x - xi) } for (int i = n2 - 1; i > 0; i--) { mul[i] = mul[i << 1 | 0].multiply(mul[i << 1 | 1]); } // mul[1] が全ての積になる // mul[1] の微分を d としたとき a_i = y_i / d(x_i) を計算したい // d(x_i) は剰余の定理を使って計算できる(multipoint_evaluate 参照) auto d = mul[1].derivative(); vector<fps> g(n2 + n2); g[1] = d.remainder_polynomial(mul[1]); for (int i = 2; i < n2 + n; i++) { g[i] = g[i >> 1].remainder_polynomial(mul[i]); } // これ以降 g の意味は \sum_{l <= j < r} (a_j \mul{l <= i < r, i != j} (x - x_i)) とする // [l, r) はセグ木の区間 for (int i = 0; i < n; i++) { g[n2 + i] = {ys[i] / g[n2 + i][0]}; } for (int i = n2 - 1; i >= 1; i--) { int lch = i << 1 | 0, rch = i << 1 | 1; g[i] = g[lch].multiply(mul[rch]) + g[rch].multiply(mul[lch]); } return g[1]; } using V = array<array<fps, 3>, 3>; mint inv2 = mint(2).inv(); mint inv3 = mint(3).inv(); V e0, e1; V mul(const V &a, const V &b) { V c; rep(i, 3) rep(j, 3) c[i][j] = fps{0}; rep(i, 3) rep(j, 3) rep(k, 3) { c[i][j] += a[i][k].multiply(b[k][j]); } return c; } V pow(int k) { if (k == 0) { return e0; } if (k == 1) { return e1; } V res = e0; if (k & 1) { res = e1; k--; } V tmp = pow(k / 2); return mul(res, mul(tmp, tmp)); } signed main() { int n, h; cin >> n >> h; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == j) { e0[i][j] = fps{1}; } else { e0[i][j] = fps{0}; } } } rep(i, 3) rep(j, 3) { e1[i][j] = fps{0}; } rep(from, 3) { if (from == 0) { e1[from][0] = fps{inv2}; e1[from][1] = fps{0, inv2}; } else if (from == 1) { e1[from][0] = fps{inv3}; e1[from][1] = fps{0, inv3}; e1[from][2] = fps{0, inv3}; } else { e1[from][1] = fps{0, inv3 * 2}; e1[from][2] = fps{0, inv3}; } } array<fps, 3> ini; ini[0] = fps{mint(2) / 5}; ini[1] = fps{0, mint(2) / 5}; ini[2] = fps{0, mint(1) / 5}; V An = pow(n - 1); fps ret; rep(from, 3) rep(to, 3) { ret += ini[from].multiply(An[from][to]); } mint ans = 0; for (int i = h; i < ret.size(); i++) { ans += ret[i]; } cout << ans.val() << endl; }