#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);
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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.

### Response

```cpp
#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);
}

```