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 uint = unsigned int;
  using cat = long long;
  using dbl = long double;
  constexpr dbl pi = 3.14159265358979323846;
  using namespace std;
  template <typename T>
  T abs(T x) {
    return (x < 0) ? (-x) : x;
  }
  cat gcd(cat a, cat b) {
    if (a > b) swap(a, b);
    while (a) {
      cat c = b % a;
      b = a;
      a = c;
    }
    return b;
  }
  cat pw(cat a, cat e, cat mod) {
    if (e <= 0) return 1;
    cat x = pw(a, e / 2, mod);
    x = x * x % mod;
    return (e & 1) ? x * a % mod : x;
  }
  template <typename T>
  class fin {
    vector<T> node_val;
    int lastone(int x) { return x & (x ^ (x - 1)); }
  
   public:
    fin(int N, T init_val) { node_val.resize(N + 10, init_val); }
    void put(int pos, T val) {
      for (int i = pos + 1; i < (int)node_val.size(); i += lastone(i))
        node_val[i] += val;
    }
    T get(int pos) {
      T ret = 0;
      for (int i = pos + 1; i > 0; i -= lastone(i)) ret += node_val[i];
      return ret;
    }
  };
  using ntt_t = long long;
  constexpr ntt_t MOD = 998244353LL;
  ntt_t proot = 3;
  vector<ntt_t> W[30];
  template <bool rev>
  inline __attribute__((always_inline)) void NTT(ntt_t *__restrict A, int N) {
    for (int i = 0, j = 0; i < N; ++i) {
      if (i < j) swap(A[i], A[j]);
      for (int k = N >> 1; (j ^= k) < k; k >>= 1) {
      }
    }
    for (int len = 1, d = 1; len != N; len *= 2, d++) {
      if (W[d].empty()) {
        W[d].resize(1 << d, 1);
        ntt_t root = pw(proot, (MOD - 1) / (1 << d), MOD);
        for (int j = 1; j < (1 << d); j++) W[d][j] = W[d][j - 1] * root % MOD;
      }
      for (int j = 0; j < N; j += 2 * len) {
        ntt_t *__restrict ptr_l = A + j;
        ntt_t *__restrict ptr_r = A + j + len;
        const ntt_t *__restrict ptr_w = W[d].data();
        for (int k = 0; k < len; k++, ptr_l++, ptr_r++, ptr_w++) {
          ntt_t u = *ptr_l, v = *ptr_r * (*ptr_w) % MOD;
          *ptr_l = u + v;
          if (*ptr_l >= MOD) *ptr_l -= MOD;
          *ptr_r = u + (MOD - v);
          if (*ptr_r >= MOD) *ptr_r -= MOD;
        }
      }
    }
    if (rev) {
      reverse(A + 1, A + N);
      ntt_t inv_N = pw(N, MOD - 2, MOD);
      for (int i = 0; i < N; ++i) A[i] = A[i] * inv_N % MOD;
    }
  }
  vector<ntt_t> convolution(vector<ntt_t> &A, vector<ntt_t> &B) {
    int sz = (int)A.size() + (int)B.size() - 1, n = 2;
    while (n < sz) n *= 2;
    constexpr int MAX_N = 1 << 21;
    static ntt_t tmp_A[MAX_N];
    memcpy(tmp_A, A.data(), sizeof(ntt_t) * A.size());
    memset(tmp_A + A.size(), 0, sizeof(ntt_t) * (n - A.size()));
    static ntt_t tmp_B[MAX_N];
    memcpy(tmp_B, B.data(), sizeof(ntt_t) * B.size());
    memset(tmp_B + B.size(), 0, sizeof(ntt_t) * (n - B.size()));
    NTT<false>(tmp_A, n);
    NTT<false>(tmp_B, n);
    for (int i = 0; i < n; i++) tmp_A[i] = tmp_A[i] * tmp_B[i] % MOD;
    NTT<true>(tmp_A, n);
    vector<ntt_t> ret(sz);
    memcpy(const_cast<ntt_t *>(ret.data()), tmp_A, sizeof(ntt_t) * sz);
    return ret;
  }
  vector<ntt_t> P(cat sz, int D) {
    vector<ntt_t> ret(D + 1, 0);
    int l = sz / 2 + 1, r = sz / 2;
    ntt_t bin_coef = 1;
    for (int k = 0; k <= sz; k++) {
      if (k > D) break;
      if ((k + 1) / 2 % 2 == 0)
        ret[k] = bin_coef;
      else
        ret[k] = MOD - bin_coef;
      if ((sz + k + 1) % 2 == 0) {
        r++;
        bin_coef = bin_coef * r % MOD;
      } else {
        l--;
        bin_coef = bin_coef * l % MOD;
      }
      bin_coef = bin_coef * pw(k + 1, MOD - 2, MOD) % MOD;
    }
    return ret;
  }
  vector<ntt_t> P_inv(cat sz, int D) {
    auto Q = P(sz, D);
    Q[0] = 0;
    for (int i = 1; i <= D; i++) Q[i] = (MOD - Q[i]) % MOD;
    auto ret = Q;
    ret[0] = 1;
    for (int pw = 2; pw <= D; pw *= 2) {
      Q = convolution(Q, Q);
      Q.resize(D + 1);
      Q[0] = 1;
      ret = convolution(ret, Q);
      ret.resize(D + 1);
      Q[0] = 0;
    }
    return ret;
  }
  int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    int N, M;
    cin >> N >> M;
    M--;
    cat ret = 0;
    auto R = P_inv(M - M / 2, N);
    if (N % 2 == 0) {
      vector<ntt_t> A = P(M - M / 2, N);
      for (int i = 0; i < N; i++) A[i] = (i + 1) * (MOD - A[i + 1]) % MOD;
      A[N] = 0;
      vector<ntt_t> B = convolution(A, R);
      ret = (ret + 2 * B[N - 1]) % MOD;
    }
    vector<ntt_t> A = P(M - M / 2 - 1, N);
    for (int i = 0; i <= N; i++)
      if ((i + 1) / 2 % 2) A[i] = (MOD - A[i]) % MOD;
    for (int i = 0; i <= N; i++)
      if (i / 2 % 2) A[i] = (MOD - A[i]) % MOD;
    vector<ntt_t> B = convolution(A, R);
    B.resize(N + 1);
    B[1] = M / 2 + 1;
    for (int i = 0; i <= N; i += 2) B[i] = 0;
    vector<ntt_t> C = B, Bp = B;
    C[0] = 1;
    for (int pw = 2; pw <= N; pw *= 2) {
      Bp = convolution(Bp, Bp);
      Bp.resize(N + 1);
      Bp[0] = 1;
      C = convolution(C, Bp);
      C.resize(N + 1);
      Bp[0] = 0;
    }
    for (int i = 1; i <= N; i += 2) ret = (ret + B[i] * C[N - i] % MOD * i) % MOD;
    cout << ret << "\n";
  }
  