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;
  int n, k, a, rev[132001 * 2], g[2][132001 * 2], ntt[132001], v1[132001],
      v2[132001], fr[132001], ifr[132001], as[132001], fg = 255, inv[132001],
                                                       vl[132001];
  int pw(int a, int p) {
    int as = 1;
    while (p) {
      if (p & 1) as = 1ll * as * a % 998244353;
      a = 1ll * a * a % 998244353;
      p >>= 1;
    }
    return as;
  }
  void init(int d) {
    fr[0] = 1;
    for (int i = 1; i <= 1 << d; i++) fr[i] = 1ll * fr[i - 1] * i % 998244353;
    ifr[1 << d] = pw(fr[1 << d], 998244353 - 2);
    for (int i = (1 << d); i >= 1; i--)
      ifr[i - 1] = 1ll * ifr[i] * i % 998244353,
              inv[i] = 1ll * fr[i - 1] * ifr[i] % 998244353;
    for (int i = 2; i <= 1 << d; i <<= 1)
      for (int j = 0; j < i; j++)
        rev[i + j] = (rev[i + (j >> 1)] >> 1) + (j & 1 ? i >> 1 : 0);
    for (int t = 0; t < 2; t++)
      for (int i = 2; i <= 1 << d; i <<= 1) {
        int tp = pw(3, 998244353 - 1 + (998244353 - 1) * (t * 2 - 1) / i);
        for (int j = 0, vl = 1; j < (i >> 1); j++, vl = 1ll * vl * tp % 998244353)
          g[t][i + j] = vl;
      }
  }
  void dft(int s, int *a, int t) {
    for (int i = 0; i < s; i++) ntt[rev[s + i]] = a[i];
    for (int l = 2; l <= s; l <<= 1)
      for (int i = 0; i < s; i += l)
        for (int j = i, st = l; j < i + (l >> 1); j++, st++) {
          int v1 = ntt[j], v2 = 1ll * ntt[j + (l >> 1)] * g[t][st] % 998244353;
          ntt[j] = (v1 + v2) % 998244353;
          ntt[j + (l >> 1)] = (v1 - v2 + 998244353) % 998244353;
        }
    int tp = t ? 1 : pw(s, 998244353 - 2);
    for (int i = 0; i < s; i++) a[i] = 1ll * ntt[i] * tp % 998244353;
  }
  vector<int> add(vector<int> a, vector<int> b) {
    vector<int> c;
    int s1 = a.size(), s2 = b.size();
    for (int i = 0; i < s1 || i < s2; i++)
      c.push_back(((i < s1 ? a[i] : 0) + (i < s2 ? b[i] : 0)) % 998244353);
    return c;
  }
  vector<int> mul(vector<int> a, vector<int> b, int n = 1e7) {
    vector<int> c;
    int s1 = a.size(), s2 = b.size();
    for (int i = 0; i < s1 + s2 - 1; i++) c.push_back(0);
    if (s1 + s2 <= fg) {
      for (int i = 0; i < s1; i++)
        for (int j = 0; j < s2; j++)
          c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % 998244353;
      while (c.size() > n) c.pop_back();
      return c;
    }
    int l = 1;
    while (l <= s1 + s2) l <<= 1;
    for (int i = 0; i < l; i++) v1[i] = v2[i] = 0;
    for (int i = 0; i < s1; i++) v1[i] = a[i];
    for (int i = 0; i < s2; i++) v2[i] = b[i];
    dft(l, v1, 1);
    dft(l, v2, 1);
    for (int i = 0; i < l; i++) v1[i] = 1ll * v1[i] * v2[i] % 998244353;
    dft(l, v1, 0);
    for (int i = 0; i < s1 + s2 - 1; i++) c[i] = v1[i];
    while (c.size() > n) c.pop_back();
    return c;
  }
  vector<int> polyinv(vector<int> a, int n) {
    while (a.size() < n) a.push_back(0);
    vector<int> b;
    for (int i = 0; i < n; i++) b.push_back(0);
    int tp = min(n, fg), st = pw(a[0], 998244353 - 2);
    for (int i = 0; i < tp; i++) {
      int vl = i ? 0 : 1;
      for (int j = 0; j < i; j++)
        vl = (vl - 1ll * b[j] * a[i - j] % 998244353 + 998244353) % 998244353;
      b[i] = 1ll * vl * st % 998244353;
    }
    if (n <= fg) return b;
    int x = 0;
    while ((n >> x) >= fg * 2 - 1) x++;
    while (1) {
      int l1 = ((n - 1) >> x) + 1, l2 = (l1 >> 1) + 1, l = 1;
      while (l <= l1 * 2 + 4) l <<= 1;
      for (int i = 0; i < l; i++) v1[i] = v2[i] = 0;
      for (int i = 0; i < l1; i++) v1[i] = a[i];
      for (int i = 0; i < l2; i++) v2[i] = b[i];
      dft(l, v1, 1);
      dft(l, v2, 1);
      for (int i = 0; i < l; i++)
        v1[i] = 1ll * v2[i] * (2 - 1ll * v1[i] * v2[i] % 998244353 + 998244353) %
                998244353;
      dft(l, v1, 0);
      for (int i = 0; i < l1; i++) b[i] = v1[i];
      if (!x) return b;
      x--;
    }
  }
  vector<int> polyln(vector<int> a, int n) {
    vector<int> v1, v2 = polyinv(a, n), as;
    for (int i = 1; i < a.size() && i <= n; i++)
      v1.push_back(1ll * a[i] * i % 998244353);
    v1 = mul(v1, v2);
    as.push_back(0);
    for (int i = 0; i < n; i++)
      as.push_back(1ll * v1[i] * inv[i + 1] % 998244353);
    return as;
  }
  int main() {
    init(17);
    scanf("%d%d", &n, &k);
    int m = k / 2;
    vl[0] = 1;
    for (int i = 1; i <= n; i++)
      if (i & 1)
        vl[i] = 1ll * vl[i - 1] * inv[i] % 998244353 * (m - i / 2) % 998244353;
      else
        vl[i] = 1ll * vl[i - 1] * inv[i] % 998244353 * (m + i / 2) % 998244353;
    vector<int> s1, s2;
    for (int i = 0; i <= n; i++) s1.push_back(i & 1 ? 0 : vl[i]);
    for (int i = 0; i <= n; i++) s2.push_back(i & 1 ? vl[i] : 0);
    s2[0] = 998244353 - 1;
    vector<int> t1 = mul(s2, polyinv(s1, n + 1), n + 1);
    for (int i = 0; i <= n; i++)
      if ((i + 3) % 4 > 1) t1[i] = (998244353 - t1[i]) % 998244353;
    if (k & 1) t1[1] = (t1[1] + 1) % 998244353;
    for (int i = 1; i <= n; i++)
      t1[i] = (i & 1) * (998244353 - t1[i]) % 998244353;
    vector<int> f1 = polyln(t1, n + 1);
    int as = 1ll * n * (998244353 - f1[n]) % 998244353;
    if (~n & 1) {
      for (int i = 2; i <= n; i++)
        if (i % 4 == 2) s1[i] = (998244353 - s1[i]) % 998244353;
      s1 = polyln(s1, n + 1);
      as = (as + 1ll * n * (998244353 - s1[n]) % 998244353) % 998244353;
    }
    printf("%d\n", as);
  }
  