description: XYMXYM and CQXYM will prepare n problems for Codeforces. The difficulty of the problem i will be an integer a_i, where a_i ≥ 0. The difficulty of the problems must satisfy a_i+a_{i+1}<m (1 ≤ i < n), and a_1+a_n<m, where m is a fixed integer. XYMXYM wants to know how many plans of the difficulty of the problems there are modulo 998 244 353.
  
  Two plans of difficulty a and b are different only if there is an integer i (1 ≤ i ≤ n) satisfying a_i ≠ b_i.
  
  Input
  
  A single line contains two integers n and m (2 ≤ n ≤ 50 000, 1 ≤ m ≤ 10^9).
  
  Output
  
  Print a single integer — the number of different plans.
  
  Examples
  
  Input
  
  
  3 2
  
  
  Output
  
  
  4
  
  
  Input
  
  
  5 9
  
  
  Output
  
  
  8105
  
  
  Input
  
  
  21038 3942834
  
  
  Output
  
  
  338529212
  
  Note
  
  In the first test case, the valid a are: [0,0,0], [0,0,1], [0,1,0], [1,0,0].
  
  [1,0,1] is invalid since a_1+a_n ≥ m.
solution: #include <bits/stdc++.h>
  using namespace std;
  const int mod = 998244353;
  inline int mul(int x, int y) { return 1ll * x * y % mod; }
  inline void sub(int &x, int y) {
    x -= y;
    if (x < 0) x += mod;
  }
  inline void pls(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
  }
  inline int dec(int x, int y) {
    x -= y;
    if (x < 0) x += mod;
    return x;
  }
  inline int add(int x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
  }
  inline int modpow(int x, long long y, int res = 1) {
    for (y = (y + mod - 1) % (mod - 1); y; y >>= 1, x = mul(x, x))
      if (y & 1) res = mul(x, res);
    return res;
  }
  char _c;
  bool _f;
  template <class T>
  inline void IN(T &x) {
    x = 0, _f = 0;
    while (_c = getchar(), !isdigit(_c))
      if (_c == '-') _f = 1;
    while (isdigit(_c)) x = x * 10 + _c - '0', _c = getchar();
    if (_f) x = -x;
  }
  template <class T>
  inline void chkmin(T &x, T y) {
    if (x > y) x = y;
  }
  template <class T>
  inline void chkmax(T &x, T y) {
    if (x < y) x = y;
  }
  const int LogN = 22;
  int tim, lim, liminv[LogN];
  vector<int> rev[LogN], w[LogN];
  inline void init_w(int len = 1 << 19) {
    w[19].resize(len), w[19][0] = 1, w[19][1] = modpow(3, (mod - 1) >> 20);
    for (int i = 2; i < len; ++i) w[19][i] = mul(w[19][i - 1], w[19][1]);
    for (int i = 18; i >= 0; --i) {
      w[i].resize(len >>= 1);
      for (int j = 0; j < len; ++j) w[i][j] = w[i + 1][j << 1];
    }
  }
  inline void init_r(int len) {
    for (lim = 1, tim = 0; lim < len; lim <<= 1, ++tim)
      ;
    if (rev[tim].size()) return;
    rev[tim].resize(lim), liminv[tim] = modpow(lim, -1);
    for (int i = 0; i < lim; ++i)
      rev[tim][i] = (rev[tim][i >> 1] >> 1) | ((i & 1) << (tim - 1));
  }
  inline void ntt(vector<int> &f, short typ) {
    static unsigned long long g[1 << 20 | 5];
    for (int i = 0; i < lim; ++i) g[rev[tim][i]] = f[i];
    for (int p = 1, s = 0, t = 0; p < lim; p <<= 1, ++t)
      for (int k = 0; k < lim; k += p << 1)
        for (int l = k; l < k + p; ++l)
          s = mul(g[l + p] % mod, w[t][l - k]), g[l + p] = g[l] + mod - s,
          g[l] += s;
    for (int i = 0; i < lim; ++i) f[i] = g[i] % mod;
    if (~typ) return;
    reverse(++f.begin(), f.end());
    for (int i = 0; i < lim; ++i) f[i] = mul(f[i], liminv[tim]);
  }
  inline vector<int> polyinv(vector<int> a, int k) {
    vector<int> b(1, modpow(a[0], -1)), c;
    for (int i = 1, l = 2, n = a.size(); i < k; i <<= 1, l <<= 1) {
      init_r(l << 1), c.resize(l);
      for (int j = 0; j < l; ++j) c[j] = j < n ? a[j] : 0;
      c.resize(lim), ntt(c, 1), b.resize(lim), ntt(b, 1);
      for (int j = 0; j < lim; ++j) b[j] = mul(b[j], dec(2, mul(c[j], b[j])));
      ntt(b, -1), b.resize(l);
    }
    return b.resize(k), b;
  }
  const int N = 5e4 + 5;
  int n, m, ans1, ans2;
  vector<int> divide(int m) {
    if (m == 1) {
      vector<int> f(n + 1);
      for (int i = 0; i <= n; ++i) f[i] = 1;
      return ans1 = 1, ans2 = 0, f;
    }
    vector<int> f = divide(m - (m + 1) / 2), g(n + 1), h(n + 1);
    f[1] = (m + 1) / 2;
    for (int i = 0; i <= n; ++i)
      if (!(i & 1)) g[i] = f[i], f[i] = 0;
    for (int i = 0; i <= n; ++i) h[i] = add(i == 0, mod - f[i]);
    h = polyinv(h, n + 1);
    ans2 = mul(2, add(ans2, ans1)), ans1 = 0;
    for (int i = 1; i <= n; ++i)
      if (i & 1) pls(ans1, mul(mul(f[i], i), h[n - i]));
    init_r(n + n + n + 1), g.resize(lim), ntt(g, 1), h.resize(lim), ntt(h, 1);
    for (int i = 0; i < lim; ++i) g[i] = mul(mul(g[i], g[i]), h[i]);
    ntt(g, -1), g.resize(n + 1);
    for (int i = 0; i <= n; ++i) pls(g[i], f[i]);
    return g;
  }
  int main() {
    init_w(), IN(n), IN(m);
    divide(m), printf("%d\n", add(ans1, mul(!(n & 1), ans2)));
    return 0;
  }
  