#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
void ADD(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void SUB(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
long long power(long long a, int b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return ans;
}
long long inv[50010];
namespace PolyOp {
const int G = 3;
int num[1 << 17], t1[1 << 17], t2[1 << 17], t3[1 << 17];
long long W[1 << 17 | 1];
int LSTN;
long long invN;
void PreCalcNTT(int N) {
  if (LSTN == N) return;
  LSTN = N, invN = power(N, mod - 2);
  for (int i = 0; i < N; i++) {
    num[i] = num[i >> 1] >> 1 | (i & 1 ? N >> 1 : 0);
  }
  W[0] = 1, W[1] = power(G, (mod - 1) / N);
  for (int i = 2; i <= N; i++) W[i] = W[i - 1] * W[1] % mod;
}
void NTT(int *f, int N, int flag) {
  PreCalcNTT(N);
  for (int i = 0; i < N; i++) {
    if (i < num[i]) swap(f[i], f[num[i]]);
  }
  for (int len = 2; len <= N; len <<= 1) {
    for (int i = 0; i < N; i += len) {
      int *fl = f + i, *fr = fl + len / 2, step = flag ? -N / len : N / len;
      long long *w = flag ? W + N : W;
      for (int j = 0; j < len / 2; j++) {
        int tmp = *fr * *w % mod;
        SUB(*fr = *fl, tmp), ADD(*fl, tmp);
        fl++, fr++, w += step;
      }
    }
  }
  if (flag) {
    for (int i = 0; i < N; i++) {
      f[i] = f[i] * invN % mod;
    }
  }
}
void polymul(int *f, int n, int *g, int m, int *h) {
  int N = 1;
  while (N < n + m - 1) N <<= 1;
  for (int(i) = (0); (i) < (N); (i)++)
    t1[i] = i < n ? f[i] : 0, t2[i] = i < m ? g[i] : 0;
  NTT(t1, N, 0), NTT(t2, N, 0);
  for (int(i) = (0); (i) < (N); (i)++) t1[i] = 1ll * t1[i] * t2[i] % mod;
  NTT(t1, N, 1);
  for (int(i) = (0); (i) < (n + m - 1); (i)++) h[i] = t1[i];
}
void polyinv(int *f, int n, int *g) {
  if (n == 1) {
    g[0] = power(f[0], mod - 2);
    return;
  }
  int mid = n + 1 >> 1;
  polyinv(f, mid, g);
  int N = 1;
  while (N < mid + mid + n - 2) N <<= 1;
  for (int i = 0; i < N; i++) {
    t1[i] = i < mid ? g[i] : 0, t2[i] = i < n ? f[i] : 0;
  }
  NTT(t1, N, 0), NTT(t2, N, 0);
  for (int i = 0; i < N; i++) {
    t1[i] = 1ll * t1[i] * t1[i] % mod * t2[i] % mod;
  }
  NTT(t1, N, 1);
  for (int i = 0; i < n; i++) {
    g[i] = ((i < mid ? g[i] : 0) * 2ll - t1[i] + mod) % mod;
  }
}
void polyln(int *f, int n, int *g) {
  polyinv(f, n, t3);
  for (int(i) = (0); (i) < (n - 1); (i)++)
    g[i] = 1ll * f[i + 1] * (i + 1) % mod;
  polymul(t3, n, g, n - 1, t3);
  for (int(i) = (0); (i) < (n); (i)++)
    g[i] = i ? t3[i - 1] * power(i, mod - 2) % mod : 0;
}
}  // namespace PolyOp
using PolyOp ::polyinv;
using PolyOp ::polyln;
using PolyOp ::polymul;
int n, m, M;
int coef[1 << 17];
int A[1 << 17], B[1 << 17], C[1 << 17], D[1 << 17], E[1 << 17], ans[1 << 17],
    res[1 << 17];
long long fac[50010], ifc[50010];
long long suc[100010], isu[100010];
long long GetProd(int l, int r) {
  return suc[l - M + 50000] * isu[r + 1 - M + 50000] % mod;
}
long long binom(int n, int k) {
  if (n < 0) return 0;
  if (k < 0 || k > n) return 0;
  return GetProd(n - k + 1, n) * ifc[k] % mod;
}
void PreCalc() {
  M = m >> 1;
  for (int i = 0; i <= 100005; i++) {
    suc[i] = (M - 50000 + i + mod) % mod;
  }
  for (int i = 100004; i >= 0; i--) {
    suc[i] = suc[i] * suc[i + 1] % mod;
  }
  for (int i = 0; i <= 100005; i++) {
    isu[i] = power(suc[i], mod - 2);
  }
  for (int i = 0; i <= 50005; i++) {
    inv[i] = power(i, mod - 2);
  }
  fac[0] = 1;
  for (int i = 1; i <= 50005; i++) fac[i] = fac[i - 1] * i % mod;
  ifc[0] = 1;
  for (int i = 1; i <= 50005; i++) ifc[i] = power(fac[i], mod - 2);
}
int main() {
  cin >> n >> m;
  PreCalc();
  for (int i = 1; i <= n; i++) {
    coef[i] = binom((m + (i & 1) >> 1) - 1 + i - (i - 1) / 2, i);
  }
  for (int i = 1; i <= n; i++) {
    A[i] = 1ll * (i % 2 == 0 ? coef[i] : 0) * (i & 2 ? 1 : mod - 1) % mod;
    B[i] = 1ll * (i % 2 == 1 ? coef[i] : 0) * (i & 2 ? mod - 1 : 1) % mod;
  }
  A[0] = (mod + 1 - A[0]) % mod;
  for (int i = 1; i <= n; i++) {
    A[i] = (mod - A[i]) % mod;
  }
  polyinv(A, n + 1, C), polymul(C, n + 1, B, n + 1, D);
  D[0] = (mod + 1 - D[0]) % mod;
  for (int(i) = (1); (i) < (n + 1); (i)++) D[i] = (mod - D[i]) % mod;
  polyinv(D, n + 1, E);
  polyln(C, n + 1, ans), polyln(E, n + 1, res);
  for (int(i) = (0); (i) < (n + 1); (i)++) ADD(ans[i], res[i]);
  printf("%lld\n", 1ll * ans[n] * n % mod);
  return 0;
}

### Prompt

Your task is to create 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;
const int mod = 998244353;
void ADD(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void SUB(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
long long power(long long a, int b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return ans;
}
long long inv[50010];
namespace PolyOp {
const int G = 3;
int num[1 << 17], t1[1 << 17], t2[1 << 17], t3[1 << 17];
long long W[1 << 17 | 1];
int LSTN;
long long invN;
void PreCalcNTT(int N) {
  if (LSTN == N) return;
  LSTN = N, invN = power(N, mod - 2);
  for (int i = 0; i < N; i++) {
    num[i] = num[i >> 1] >> 1 | (i & 1 ? N >> 1 : 0);
  }
  W[0] = 1, W[1] = power(G, (mod - 1) / N);
  for (int i = 2; i <= N; i++) W[i] = W[i - 1] * W[1] % mod;
}
void NTT(int *f, int N, int flag) {
  PreCalcNTT(N);
  for (int i = 0; i < N; i++) {
    if (i < num[i]) swap(f[i], f[num[i]]);
  }
  for (int len = 2; len <= N; len <<= 1) {
    for (int i = 0; i < N; i += len) {
      int *fl = f + i, *fr = fl + len / 2, step = flag ? -N / len : N / len;
      long long *w = flag ? W + N : W;
      for (int j = 0; j < len / 2; j++) {
        int tmp = *fr * *w % mod;
        SUB(*fr = *fl, tmp), ADD(*fl, tmp);
        fl++, fr++, w += step;
      }
    }
  }
  if (flag) {
    for (int i = 0; i < N; i++) {
      f[i] = f[i] * invN % mod;
    }
  }
}
void polymul(int *f, int n, int *g, int m, int *h) {
  int N = 1;
  while (N < n + m - 1) N <<= 1;
  for (int(i) = (0); (i) < (N); (i)++)
    t1[i] = i < n ? f[i] : 0, t2[i] = i < m ? g[i] : 0;
  NTT(t1, N, 0), NTT(t2, N, 0);
  for (int(i) = (0); (i) < (N); (i)++) t1[i] = 1ll * t1[i] * t2[i] % mod;
  NTT(t1, N, 1);
  for (int(i) = (0); (i) < (n + m - 1); (i)++) h[i] = t1[i];
}
void polyinv(int *f, int n, int *g) {
  if (n == 1) {
    g[0] = power(f[0], mod - 2);
    return;
  }
  int mid = n + 1 >> 1;
  polyinv(f, mid, g);
  int N = 1;
  while (N < mid + mid + n - 2) N <<= 1;
  for (int i = 0; i < N; i++) {
    t1[i] = i < mid ? g[i] : 0, t2[i] = i < n ? f[i] : 0;
  }
  NTT(t1, N, 0), NTT(t2, N, 0);
  for (int i = 0; i < N; i++) {
    t1[i] = 1ll * t1[i] * t1[i] % mod * t2[i] % mod;
  }
  NTT(t1, N, 1);
  for (int i = 0; i < n; i++) {
    g[i] = ((i < mid ? g[i] : 0) * 2ll - t1[i] + mod) % mod;
  }
}
void polyln(int *f, int n, int *g) {
  polyinv(f, n, t3);
  for (int(i) = (0); (i) < (n - 1); (i)++)
    g[i] = 1ll * f[i + 1] * (i + 1) % mod;
  polymul(t3, n, g, n - 1, t3);
  for (int(i) = (0); (i) < (n); (i)++)
    g[i] = i ? t3[i - 1] * power(i, mod - 2) % mod : 0;
}
}  // namespace PolyOp
using PolyOp ::polyinv;
using PolyOp ::polyln;
using PolyOp ::polymul;
int n, m, M;
int coef[1 << 17];
int A[1 << 17], B[1 << 17], C[1 << 17], D[1 << 17], E[1 << 17], ans[1 << 17],
    res[1 << 17];
long long fac[50010], ifc[50010];
long long suc[100010], isu[100010];
long long GetProd(int l, int r) {
  return suc[l - M + 50000] * isu[r + 1 - M + 50000] % mod;
}
long long binom(int n, int k) {
  if (n < 0) return 0;
  if (k < 0 || k > n) return 0;
  return GetProd(n - k + 1, n) * ifc[k] % mod;
}
void PreCalc() {
  M = m >> 1;
  for (int i = 0; i <= 100005; i++) {
    suc[i] = (M - 50000 + i + mod) % mod;
  }
  for (int i = 100004; i >= 0; i--) {
    suc[i] = suc[i] * suc[i + 1] % mod;
  }
  for (int i = 0; i <= 100005; i++) {
    isu[i] = power(suc[i], mod - 2);
  }
  for (int i = 0; i <= 50005; i++) {
    inv[i] = power(i, mod - 2);
  }
  fac[0] = 1;
  for (int i = 1; i <= 50005; i++) fac[i] = fac[i - 1] * i % mod;
  ifc[0] = 1;
  for (int i = 1; i <= 50005; i++) ifc[i] = power(fac[i], mod - 2);
}
int main() {
  cin >> n >> m;
  PreCalc();
  for (int i = 1; i <= n; i++) {
    coef[i] = binom((m + (i & 1) >> 1) - 1 + i - (i - 1) / 2, i);
  }
  for (int i = 1; i <= n; i++) {
    A[i] = 1ll * (i % 2 == 0 ? coef[i] : 0) * (i & 2 ? 1 : mod - 1) % mod;
    B[i] = 1ll * (i % 2 == 1 ? coef[i] : 0) * (i & 2 ? mod - 1 : 1) % mod;
  }
  A[0] = (mod + 1 - A[0]) % mod;
  for (int i = 1; i <= n; i++) {
    A[i] = (mod - A[i]) % mod;
  }
  polyinv(A, n + 1, C), polymul(C, n + 1, B, n + 1, D);
  D[0] = (mod + 1 - D[0]) % mod;
  for (int(i) = (1); (i) < (n + 1); (i)++) D[i] = (mod - D[i]) % mod;
  polyinv(D, n + 1, E);
  polyln(C, n + 1, ans), polyln(E, n + 1, res);
  for (int(i) = (0); (i) < (n + 1); (i)++) ADD(ans[i], res[i]);
  printf("%lld\n", 1ll * ans[n] * n % mod);
  return 0;
}

```