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;
  inline int M(int x) { return (x >= 998244353) ? (x - 998244353) : x; }
  inline int M1(int x) { return (x < 0) ? (x + 998244353) : x; }
  inline int ksm(int p, int k) {
    int res = 1;
    while (k) {
      if (k & 1) res = 1ll * res * p % 998244353;
      k >>= 1;
      p = 1ll * p * p % 998244353;
    }
    return res;
  }
  int wn[262145], rev[262145 << 1];
  inline void Make(int u) {
    int i, j, w, len = 1;
    while (len <= u) len <<= 1;
    for (i = 1; i < len; i <<= 1) {
      w = ksm(3, (998244353 - 1) / (i << 1));
      wn[i] = 1;
      for (j = 1; j < i; j++) wn[i + j] = 1ll * wn[i + j - 1] * w % 998244353;
    }
    for (i = 1; i <= len; i <<= 1)
      for (j = 0; j < i; j++)
        rev[i + j] = (rev[i + (j >> 1)] >> 1) | ((j & 1) * (i >> 1));
  }
  inline void NTT(int deal[], int len, int opt) {
    int i, j, k, x, y;
    for (i = 0; i < len; i++)
      if (i > rev[len + i]) swap(deal[i], deal[rev[len + i]]);
    for (i = 1; i < len; i <<= 1)
      for (j = 0; j < len; j += (i << 1))
        for (k = 0; k < i; k++)
          x = deal[j + k], y = 1ll * wn[i + k] * deal[i + j + k] % 998244353,
          deal[j + k] = M(x + y), deal[i + j + k] = M1(x - y);
    if (!opt) {
      int inv = 998244353 - (998244353 / len);
      for (i = 0; i < len; i++) deal[i] = 1ll * deal[i] * inv % 998244353;
      reverse(deal + 1, deal + len);
    }
  }
  inline int Getl(int u) {
    int len = 1;
    while (len <= u) len <<= 1;
    return len;
  }
  int fac[262145], inv[262145], I[262145], t1[262145], t2[262145], t3[262145],
      t4[262145];
  void INV(int *A, int *B, int n) {
    if (n == 1) {
      B[0] = ksm(A[0], 998244353 - 2);
      return;
    }
    int i, mid = (n + 1) >> 1, l1 = Getl(mid - 1 + n - 1), l2 = Getl(n - 1);
    INV(A, B, mid);
    if (51 * l1 < 80 * l2) {
      memcpy(t1, A, sizeof(int) * n);
      memcpy(t2, B, sizeof(int) * mid);
      NTT(t1, l1, 1);
      NTT(t2, l1, 1);
      for (i = 0; i < l1; i++)
        t1[i] = M1(-1ll * t2[i] * t1[i] % 998244353 * t2[i] % 998244353);
      NTT(t1, l1, 0);
      memcpy(B + mid, t1 + mid, sizeof(int) * (n - mid));
      memset(t1, 0, sizeof(int) * l1);
      memset(t2, 0, sizeof(int) * l1);
    } else {
      memcpy(t1, A, sizeof(int) * n);
      memcpy(t2, B, sizeof(int) * mid);
      NTT(t1, l2, 1);
      NTT(t2, l2, 1);
      for (i = 0; i < l2; i++) t1[i] = M1(-1ll * t1[i] * t2[i] % 998244353);
      NTT(t1, l2, 0);
      memset(t1, 0, sizeof(int) * mid);
      NTT(t1, l2, 1);
      for (i = 0; i < l2; i++) t1[i] = 1ll * t1[i] * t2[i] % 998244353;
      NTT(t1, l2, 0);
      memcpy(B + mid, t1 + mid, sizeof(int) * (n - mid));
      memset(t1, 0, sizeof(int) * l2);
      memset(t2, 0, sizeof(int) * l2);
    }
  }
  inline void Der(int *A, int *B, int n) {
    for (int i = 1; i < n; i++) B[i - 1] = 1ll * i * A[i] % 998244353;
    B[n - 1] = 0;
  }
  inline void Int(int *A, int *B, int n) {
    B[0] = 0;
    for (int i = 0; i < n - 1; i++) B[i + 1] = 1ll * A[i] * I[i + 1] % 998244353;
  }
  int n, m, hf, f[262145], g[262145], ls[262145], fr[262145];
  inline void LNH(int *A, int *B, int n) {
    for (int i = 0; i <= n; i++) t3[i] = 1ll * A[i] * (m - i) % 998244353;
    INV(A, t4, n);
    int i, len = Getl(n - 1 + n - 1);
    NTT(t3, len, 1);
    NTT(t4, len, 1);
    for (i = 0; i < len; i++) B[i] = 1ll * t3[i] * t4[i] % 998244353;
    NTT(B, len, 0);
    memset(t3, 0, sizeof(int) * len);
    memset(t4, 0, sizeof(int) * len);
  }
  inline int dwk(int x, int k) {
    return 1ll * fr[x - hf] * ls[k - (x - hf)] % 998244353;
  }
  inline int sg(int x) {
    x = (x >> 1) + x;
    return (x & 1) ? (998244353 - 1) : 1;
  }
  int main() {
    Make(200000);
    fac[0] = 1;
    for (int i = 1; i < 262145; i++) fac[i] = 1ll * fac[i - 1] * i % 998244353;
    inv[262145 - 1] = ksm(fac[262145 - 1], 998244353 - 2);
    for (int i = 262145 - 2; i >= 0; i--)
      inv[i] = 1ll * inv[i + 1] * (i + 1) % 998244353;
    scanf("%d%d", &n, &m);
    hf = m >> 1;
    int i;
    fr[0] = ls[0] = 1;
    for (i = 1; i <= n; i++)
      ls[i] = 1ll * ls[i - 1] * (hf - i + 1) % 998244353,
      fr[i] = 1ll * fr[i - 1] * (hf + i) % 998244353;
    if (m & 1) {
      for (i = 0; i <= n; i++)
        f[i] = 1ll *
               ((i & 1)
                    ? (1ll * inv[i] * dwk(hf + ((i - 1) >> 1) + 1, i) % 998244353)
                    : (1ll * inv[i] * dwk(hf + (i >> 1), i) % 998244353) %
                          998244353) *
               sg(i) % 998244353;
    } else {
      for (i = 0; i <= n; i++)
        f[i] = 1ll *
               ((i & 1) ? (1ll * inv[i] * dwk(hf + ((i - 1) >> 1), i) % 998244353)
                        : (1ll * inv[i] * dwk(hf + (i >> 1), i) % 998244353) %
                              998244353) *
               sg(i) % 998244353;
    }
    LNH(f, g, n + 1);
    printf("%d", g[n]);
    return 0;
  }
  