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 maxn = 131072, P = 998244353;
  int n, m, inv[maxn];
  int lim, L, r[maxn], w[maxn];
  int fst_pow(int a, int k) {
    long long res = 1, t = a;
    while (k) {
      if (k & 1) {
        res = res * t % P;
      }
      t = t * t % P;
      k >>= 1;
    }
    return res;
  }
  void init(int n) {
    for (lim = 1, L = 0; lim < n; lim <<= 1) L++;
    for (int i = 0; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    w[lim >> 1] = 1;
    int t = fst_pow(3, (P - 1) / lim);
    for (int i = (lim >> 1) + 1; i < lim; i++) w[i] = 1LL * w[i - 1] * t % P;
    for (int i = (lim >> 1) - 1; i > 0; i--) w[i] = w[i << 1];
  }
  void NTT(int *a, int type) {
    static unsigned long long c[maxn];
    copy(a, a + lim, c);
    for (int i = 0; i < lim; i++)
      if (i < r[i]) swap(c[i], c[r[i]]);
    for (int i = 1; i < lim; i <<= 1) {
      for (int j = 0; j < lim; j += i << 1) {
        for (int k = 0; k < i; k++) {
          unsigned long long t = c[i + j + k] * w[i + k] % P;
          c[i + j + k] = c[j + k] + P - t, c[j + k] += t;
        }
      }
    }
    if (!~type) {
      reverse(c + 1, c + lim);
      for (int i = 0, t = fst_pow(lim, P - 2); i < lim; i++)
        c[i] = c[i] % P * t % P;
    }
    for (int i = 0; i < lim; i++) a[i] = c[i] % P;
  }
  vector<int> operator*(vector<int> A, vector<int> B) {
    int len = A.size() + B.size() - 1;
    init(len), A.resize(lim), B.resize(lim);
    NTT(A.data(), 1), NTT(B.data(), 1);
    for (int i = 0; i < lim; i++) A[i] = 1LL * A[i] * B[i] % P;
    NTT(A.data(), -1), A.resize(len);
    return A;
  }
  vector<int> poly_inv(vector<int> A) {
    if (A.size() == 1) return {fst_pow(A[0], P - 2)};
    int m = (A.size() + 1) / 2;
    vector<int> B = poly_inv({A.begin(), A.begin() + m}), C = A * B;
    C.resize(A.size()), fill(C.begin(), C.begin() + m, 0);
    vector<int> ans = B;
    ans.resize(A.size()), C = C * B;
    for (int i = m; i < A.size(); i++) ans[i] = (P - C[i]) % P;
    return ans;
  }
  int main() {
    scanf("%d %d", &n, &m);
    for (int i = inv[0] = 1; i <= n; i++) {
      inv[i] = fst_pow(i, P - 2);
    }
    if ((n & 1) == 0) {
      vector<int> F(n / 2 + 1), G(n / 2 + 1);
      F[0] = 1;
      for (int i = 1; i <= n / 2; i++) {
        F[i] = 1LL * F[i - 1] * (m - i + 1) % P * (m + i) % P * inv[2 * i - 1] %
               P * inv[2 * i] % P;
        G[i] = 1LL * (P - i) * F[i] % P;
      }
      F = G * poly_inv(F);
      printf("%lld\n", 1LL * F[n / 2] * (n & 2 ? P - 1 : 1) % P);
    } else {
      vector<int> F(n / 2 + 1);
      for (int i = 1; i <= n / 2; i++) {
        F[i] = 1LL * (i > 1 ? F[i - 1] : P - 1) * (m / 2 - i + 1) % P *
               (m / 2 + i) % P * inv[2 * i - 1] % P * inv[2 * i] % P;
      }
      vector<int> fir(n / 2 + 2);
      fir[1] = (P - m / 2) % P;
      for (int i = 2; i <= n / 2 + 1; i++) {
        fir[i] = 1LL * fir[i - 1] * (m / 2 - i + 1) % P * (m / 2 + i - 1) % P *
                 inv[2 * i - 2] % P * inv[2 * i - 1] % P;
      }
      F[0] = 1;
      for (int i = 1; i <= n / 2; i++) {
        F[i] = (P - F[i]) % P;
      }
      vector<int> odd = fir * poly_inv(F);
      if (m % 2) odd[1] = P - m / 2 - 1;
      F = vector<int>(n + 1);
      for (int i = 1; i <= n && i / 2 + 1 < odd.size(); i += 2) {
        F[i] = odd[i / 2 + 1];
        if (!(i / 2 % 2)) F[i] = (P - F[i]) % P;
      }
      vector<int> G = F;
      for (int i = 1; i <= n; i++) {
        G[i] = 1LL * i * G[i] % P;
      }
      F[0] = 1;
      for (int i = 1; i <= n; i++) {
        F[i] = (P - F[i]) % P;
      }
      F = G * poly_inv(F);
      printf("%d\n", F[n]);
    }
    return 0;
  }
  