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>
  unsigned long long tmp[131073], invn;
  int a_[131072];
  inline int ksm(unsigned long long a, int b) {
    int ans = 1;
    while (b)
      (b & 1) && (ans = a * ans % 998244353), a = a * a % 998244353, b >>= 1;
    return ans;
  }
  void init(int n) {
    for (int i = 1; i < n; i++)
      a_[i] = i & 1 ? a_[i ^ 1] | n >> 1 : a_[i >> 1] >> 1;
    for (int i = tmp[0] = 1, j = ksm(3, (998244353 - 1) / n); i <= n; i++)
      tmp[i] = tmp[i - 1] * j % 998244353;
    invn = ksm(n, 998244353 - 2);
  }
  void ntt(int a[], int n, bool typ) {
    int p;
    for (int i = 1; i < n; i++)
      if (a_[i] < i) p = a[i], a[i] = a[a_[i]], a[a_[i]] = p;
    if (typ)
      for (int i = 1, d = n >> 1; d; i <<= 1, d >>= 1)
        for (int j = 0; j < n; j += i << 1)
          for (int k = 0; k < i; k++)
            p = tmp[n - d * k] * a[i + j + k] % 998244353,
            (a[i + j + k] = a[j + k] + 998244353 - p) >= 998244353 &&
                (a[i + j + k] -= 998244353),
            (a[j + k] += p) >= 998244353 && (a[j + k] -= 998244353);
    else
      for (int i = 1, d = n >> 1; d; i <<= 1, d >>= 1)
        for (int j = 0; j < n; j += i << 1)
          for (int k = 0; k < i; k++)
            p = tmp[d * k] * a[i + j + k] % 998244353,
            (a[i + j + k] = a[j + k] + 998244353 - p) >= 998244353 &&
                (a[i + j + k] -= 998244353),
            (a[j + k] += p) >= 998244353 && (a[j + k] -= 998244353);
    if (typ)
      for (int i = 0; i < n; i++) a[i] = invn * a[i] % 998244353;
  }
  void getinv(int n, int a[], int b[]) {
    static int tmp[131072];
    memset(b, 0, sizeof(int) * (n << 1));
    b[0] = ksm(a[0], 998244353 - 2);
    for (int i = 1; i < n; i <<= 1) {
      init(i << 2);
      memset(tmp, 0, sizeof(int) * (i << 2));
      memcpy(tmp, a, sizeof(int) * (i << 1));
      ntt(tmp, i << 2, 0);
      ntt(b, i << 2, 0);
      for (int j = 0; j < i << 2; j++)
        b[j] = (1ull * (998244353 - tmp[j]) * b[j] % 998244353 + 2) * b[j] %
               998244353;
      ntt(b, i << 2, 1);
      memset(b + (i << 1), 0, sizeof(int) * (i << 1));
    }
  }
  int n, m, a[131072], b[131072], d0[131072], d1[131072], len, ans;
  void work(int v) {
    if (v == 1) {
      for (int i = 0; i < len; i++) a[i] = 1;
      ans = 1;
      return;
    }
    work(v >> 1);
    memset(d0, 0, sizeof(int) * (len << 1));
    memset(d1, 0, sizeof(int) * (len << 1));
    for (int i = 0; i < len; i++) (i & 1 ? d1 : d0)[i] = a[i];
    if (v & 1) ++d1[1] == 998244353 && (d1[1] = 0);
    memset(a, 0, sizeof(int) * (len << 1));
    for (int i = 0; i < len; i++) a[i] = d1[i] ? 998244353 - d1[i] : 0;
    ++a[0] == 998244353 && (a[0] = 0);
    getinv(len, a, b);
    if (v == m || !(n & 1)) {
      int Ans = 0;
      for (int i = 1; i <= n; i += 2)
        Ans = (1ull * d1[i] * b[n - i] % 998244353 * i + Ans) % 998244353;
      if (!(n & 1))
        ans = (2ull * ans + Ans) % 998244353;
      else
        ans = Ans;
      if (v == m) return;
    }
    init(len << 1);
    ntt(d0, len << 1, 0);
    for (int i = 0; i < len << 1; i++) d0[i] = 1ull * d0[i] * d0[i] % 998244353;
    ntt(d0, len << 1, 1);
    memset(d0 + len, 0, sizeof(int) * len);
    ntt(d0, len << 1, 0);
    ntt(b, len << 1, 0);
    for (int i = 0; i < len << 1; i++) a[i] = 1ull * d0[i] * b[i] % 998244353;
    ntt(a, len << 1, 1);
    for (int i = 1; i < len; i += 2)
      (a[i] += d1[i]) >= 998244353 && (a[i] -= 998244353);
    if (v & 1) a[1] ? a[1]-- : a[1] = 998244353 - 1;
  }
  int main() {
    scanf("%d%d", &n, &m);
    len = n << 1;
    while (len ^ len & -len) len ^= len & -len;
    work(m);
    printf("%d\n", ans);
  }
  