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 long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && (c != '-')) c = getchar();
    if (c == '-') f = -1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
  }
  namespace Poly {
  const int mod = 998244353;
  inline int Add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
  inline int Del(int a, int b) { return a >= b ? a - b : a + mod - b; }
  inline int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
      if (b & 1) ret = 1ll * ret * a % mod;
    return ret;
  }
  inline int Get(int x) {
    int ret = 1;
    while (ret < x) ret <<= 1;
    return ret;
  }
  vector<int> pos, w;
  inline void init(int n) {
    pos.resize(n), w.resize(n);
    for (int i = (0); i <= (n - 1); i++)
      pos[i] = (pos[i >> 1] >> 1) | ((i & 1) * (n >> 1));
    for (int i = 1; i < n; i <<= 1) {
      int wn = power(3, (mod - 1) / i / 2);
      w[i] = 1;
      for (int j = (1); j <= (i - 1); j++)
        w[j + i] = 1ll * w[j + i - 1] * wn % mod;
    }
  }
  inline void DFT(vector<int> &F, int n) {
    F.resize(n);
    for (int i = (0); i <= (n - 1); i++)
      if (i < pos[i]) swap(F[i], F[pos[i]]);
    for (int i = 1; i < n; i <<= 1)
      for (int j = 0; j < n; j += i << 1)
        for (int k = 0; k < i; k++) {
          int x = F[j + k], y = 1ll * F[j + k + i] * w[i + k] % mod;
          F[j + k] = Add(x, y), F[j + k + i] = Del(x, y);
        }
  }
  inline void IDFT(vector<int> &F, int n) {
    DFT(F, n), reverse(F.begin() + 1, F.end());
    for (int i = 0, inv = power(n, mod - 2); i < n; i++)
      F[i] = 1ll * F[i] * inv % mod;
  }
  inline vector<int> Del(vector<int> A, vector<int> B) {
    int n = max(A.size(), B.size());
    vector<int> ret(n);
    A.resize(n), B.resize(n);
    for (int i = (0); i <= (n - 1); i++) ret[i] = Del(A[i], B[i]);
    return ret;
  }
  inline vector<int> Add(vector<int> A, vector<int> B) {
    int n = max(A.size(), B.size());
    vector<int> ret(n);
    A.resize(n), B.resize(n);
    for (int i = (0); i <= (n - 1); i++) ret[i] = Add(A[i], B[i]);
    return ret;
  }
  inline vector<int> Mul(vector<int> A, vector<int> B) {
    if (A.size() <= 20 || B.size() <= 20) {
      vector<int> ret;
      ret.resize(A.size() + B.size() - 1);
      for (int i = (0); i < (((int)(A).size())); i++)
        for (int j = (0); j < (((int)(B).size())); j++)
          ret[i + j] = Add(ret[i + j], 1ll * A[i] * B[j] % mod);
      return ret;
    }
    int n = A.size() + B.size() - 1, m = Get(n);
    init(m);
    DFT(A, m), DFT(B, m);
    for (int i = (0); i <= (m - 1); i++) A[i] = 1ll * A[i] * B[i] % mod;
    return IDFT(A, m), A.resize(n), A;
  }
  inline vector<int> Inv(const vector<int> &F, int n) {
    if (n == 1) return {power(F[0], mod - 2)};
    vector<int> G = Inv(F, n + 1 >> 1), tmp(F.begin(), F.begin() + n);
    int m = Get(n * 2 - 1);
    init(m);
    DFT(G, m), DFT(tmp, m);
    for (int i = (0); i <= (m - 1); i++)
      G[i] = 1ll * Del(2, 1ll * G[i] * tmp[i] % mod) * G[i] % mod;
    return IDFT(G, m), G.resize(n), G;
  }
  }  // namespace Poly
  const int mod = 998244353;
  pair<vector<int>, int> solve(int n, int m) {
    if (!m) {
      vector<int> F(n + 1);
      return F[0] = 1, make_pair(F, 0);
    }
    auto [tmp, ans] = solve(n, m / 2);
    vector<int> odd(n + 1), even(n + 1);
    for (int i = (0); i <= (n); i++)
      if (i & 1)
        odd[i] = tmp[i];
      else
        even[i] = tmp[i];
    odd[1] = (m + 1) / 2;
    vector<int> F(n + 1);
    F[0] = 1;
    for (int i = (1); i <= (n); i++) F[i] = mod - odd[i];
    F = Poly::Inv(F, n + 1);
    if (n % 2 == 0)
      ans = (ans * 2ll + F[n]) % mod;
    else
      ans = F[n];
    for (int i = (1); i <= (n); i++)
      if (i & 1) ans = (ans + 1ll * odd[i] * (i - 1) % mod * F[n - i]) % mod;
    vector<int> G = Poly::Mul(Poly::Mul(even, even), F);
    G.resize(n + 1);
    G = Poly::Add(G, odd);
    return make_pair(G, ans);
  }
  int main() {
    int n = read(), m = read();
    printf("%d\n", solve(n, m).second);
  }
  