#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int mod = 998244353;
const int G = 3, Gi = 332748118;
int add(int x, int y) {
  if ((x += y) >= mod) x -= mod;
  return x;
}
int sub(int x, int y) {
  if ((x -= y) < 0) x += mod;
  return x;
}
int qpow(int a, int b = mod - 2) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}
namespace Poly {
vector<int> Rev, W;
int lim, L;
void getR(int len) {
  lim = 1, L = 0;
  while (lim <= len) lim <<= 1, L++;
  Rev.resize(lim), W.resize(lim), W[0] = 1;
  for (int i = 0; i < lim; i++)
    Rev[i] = (Rev[i >> 1] >> 1) | ((i & 1) << L - 1);
}
void wf(vector<int> &a) {
  int n = a.size();
  for (int i = 0; i < n; i++) a[i] = 1ll * (i + 1) * a[i + 1] % mod;
  a[n - 1] = 0;
}
void jf(vector<int> &a) {
  int n = a.size();
  for (int i = n - 1; i >= 1; i--) a[i] = 1ll * a[i - 1] * qpow(i) % mod;
  a[0] = 0;
}
void NTT(vector<int> &a, int opt) {
  for (int i = 0; i < lim; i++)
    if (i < Rev[i]) swap(a[i], a[Rev[i]]);
  for (int mid = 1; mid < lim; mid <<= 1) {
    int Wn = qpow(opt == 1 ? G : Gi, (mod - 1) / (mid << 1));
    for (int k = 1; k < mid; k++) W[k] = 1ll * W[k - 1] * Wn % mod;
    for (int j = 0; j < lim; j += mid << 1) {
      for (int k = 0; k < mid; k++) {
        int x = a[j + k], y = 1ll * W[k] * a[j + k + mid] % mod;
        a[j + k] = add(x, y);
        a[j + k + mid] = sub(x, y);
      }
    }
  }
  if (opt == -1) {
    int linv = qpow(lim);
    for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * linv % mod;
  }
}
vector<int> operator*(vector<int> a, vector<int> b) {
  int len = a.size() + b.size() - 1;
  getR(len);
  a.resize(lim), b.resize(lim);
  NTT(a, 1), NTT(b, 1);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % mod;
  NTT(a, -1);
  a.resize(len);
  return a;
}
vector<int> Inv(vector<int> a) {
  if (int(a.size()) == 1) return vector<int>(1, qpow(a[0]));
  int len = a.size();
  vector<int> ta = a;
  ta.resize((len + 1) / 2);
  vector<int> tb = Inv(ta);
  getR(2 * len), a.resize(lim), tb.resize(lim);
  NTT(a, 1), NTT(tb, 1);
  for (int i = 0; i < lim; i++)
    tb[i] = 1ll * tb[i] * (mod + 2 - 1ll * a[i] * tb[i] % mod) % mod;
  NTT(tb, -1);
  tb.resize(len);
  return tb;
}
vector<int> Ln(vector<int> a) {
  vector<int> ta = a;
  wf(ta);
  int len = a.size();
  a = ta * Inv(a), jf(a);
  a.resize(len);
  return a;
}
vector<int> Exp(vector<int> a) {
  if (int(a.size()) == 1) return vector<int>(1, 1);
  int len = a.size();
  vector<int> ta = a;
  ta.resize((len + 1) / 2);
  vector<int> tb = Exp(ta);
  tb.resize(len);
  vector<int> Lnb = Ln(tb);
  assert(Lnb.size() == len);
  for (int i = 0; i < len; i++) Lnb[i] = (a[i] - Lnb[i] + mod) % mod;
  Lnb[0] = (Lnb[0] + 1) % mod;
  tb = tb * Lnb;
  tb.resize(len);
  return tb;
}
}  // namespace Poly
using namespace Poly;
const int N = 300005;
int fac[N], ifac[N], inv[N];
inline void init(int n) {
  inv[1] = 1;
  for (int i = 2; i <= n; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  ifac[n] = qpow(fac[n]);
  for (int i = n; i >= 1; i--) ifac[i - 1] = 1ll * ifac[i] * i % mod;
}
inline int C(int n, int m) {
  return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
int n, m;
void rev(vector<int> &a) {
  a[0] = 1;
  for (int i = 1; i <= int(a.size()) - 1; i++) a[i] = (mod - a[i]) % mod;
}
int main() {
  init(N - 5);
  cin >> n >> m;
  vector<int> a(n + 1), b(n + 1);
  int cur = 1;
  for (int i = 1; i <= n; i++) {
    int t = (m + i) / 2;
    if ((m + i) & 1)
      cur = 1ll * cur * (t - i + 1) % mod;
    else
      cur = 1ll * cur * t % mod;
    cur = 1ll * cur * inv[i] % mod;
    if (i & 1)
      b[i] = ((i / 2) & 1 ? -1 : 1) * cur;
    else
      a[i] = ((i / 2) & 1 ? 1 : -1) * cur;
    a[i] = (a[i] + mod) % mod;
    b[i] = (b[i] + mod) % mod;
  }
  rev(a);
  vector<int> c = b * Inv(a);
  rev(c);
  vector<int> f = Ln(Inv(a));
  vector<int> g = Ln(Inv(c));
  print(1ll * n * (f[n] + g[n]) % mod, '\n');
  return 0;
}

### 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>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int mod = 998244353;
const int G = 3, Gi = 332748118;
int add(int x, int y) {
  if ((x += y) >= mod) x -= mod;
  return x;
}
int sub(int x, int y) {
  if ((x -= y) < 0) x += mod;
  return x;
}
int qpow(int a, int b = mod - 2) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}
namespace Poly {
vector<int> Rev, W;
int lim, L;
void getR(int len) {
  lim = 1, L = 0;
  while (lim <= len) lim <<= 1, L++;
  Rev.resize(lim), W.resize(lim), W[0] = 1;
  for (int i = 0; i < lim; i++)
    Rev[i] = (Rev[i >> 1] >> 1) | ((i & 1) << L - 1);
}
void wf(vector<int> &a) {
  int n = a.size();
  for (int i = 0; i < n; i++) a[i] = 1ll * (i + 1) * a[i + 1] % mod;
  a[n - 1] = 0;
}
void jf(vector<int> &a) {
  int n = a.size();
  for (int i = n - 1; i >= 1; i--) a[i] = 1ll * a[i - 1] * qpow(i) % mod;
  a[0] = 0;
}
void NTT(vector<int> &a, int opt) {
  for (int i = 0; i < lim; i++)
    if (i < Rev[i]) swap(a[i], a[Rev[i]]);
  for (int mid = 1; mid < lim; mid <<= 1) {
    int Wn = qpow(opt == 1 ? G : Gi, (mod - 1) / (mid << 1));
    for (int k = 1; k < mid; k++) W[k] = 1ll * W[k - 1] * Wn % mod;
    for (int j = 0; j < lim; j += mid << 1) {
      for (int k = 0; k < mid; k++) {
        int x = a[j + k], y = 1ll * W[k] * a[j + k + mid] % mod;
        a[j + k] = add(x, y);
        a[j + k + mid] = sub(x, y);
      }
    }
  }
  if (opt == -1) {
    int linv = qpow(lim);
    for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * linv % mod;
  }
}
vector<int> operator*(vector<int> a, vector<int> b) {
  int len = a.size() + b.size() - 1;
  getR(len);
  a.resize(lim), b.resize(lim);
  NTT(a, 1), NTT(b, 1);
  for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % mod;
  NTT(a, -1);
  a.resize(len);
  return a;
}
vector<int> Inv(vector<int> a) {
  if (int(a.size()) == 1) return vector<int>(1, qpow(a[0]));
  int len = a.size();
  vector<int> ta = a;
  ta.resize((len + 1) / 2);
  vector<int> tb = Inv(ta);
  getR(2 * len), a.resize(lim), tb.resize(lim);
  NTT(a, 1), NTT(tb, 1);
  for (int i = 0; i < lim; i++)
    tb[i] = 1ll * tb[i] * (mod + 2 - 1ll * a[i] * tb[i] % mod) % mod;
  NTT(tb, -1);
  tb.resize(len);
  return tb;
}
vector<int> Ln(vector<int> a) {
  vector<int> ta = a;
  wf(ta);
  int len = a.size();
  a = ta * Inv(a), jf(a);
  a.resize(len);
  return a;
}
vector<int> Exp(vector<int> a) {
  if (int(a.size()) == 1) return vector<int>(1, 1);
  int len = a.size();
  vector<int> ta = a;
  ta.resize((len + 1) / 2);
  vector<int> tb = Exp(ta);
  tb.resize(len);
  vector<int> Lnb = Ln(tb);
  assert(Lnb.size() == len);
  for (int i = 0; i < len; i++) Lnb[i] = (a[i] - Lnb[i] + mod) % mod;
  Lnb[0] = (Lnb[0] + 1) % mod;
  tb = tb * Lnb;
  tb.resize(len);
  return tb;
}
}  // namespace Poly
using namespace Poly;
const int N = 300005;
int fac[N], ifac[N], inv[N];
inline void init(int n) {
  inv[1] = 1;
  for (int i = 2; i <= n; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  ifac[n] = qpow(fac[n]);
  for (int i = n; i >= 1; i--) ifac[i - 1] = 1ll * ifac[i] * i % mod;
}
inline int C(int n, int m) {
  return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
int n, m;
void rev(vector<int> &a) {
  a[0] = 1;
  for (int i = 1; i <= int(a.size()) - 1; i++) a[i] = (mod - a[i]) % mod;
}
int main() {
  init(N - 5);
  cin >> n >> m;
  vector<int> a(n + 1), b(n + 1);
  int cur = 1;
  for (int i = 1; i <= n; i++) {
    int t = (m + i) / 2;
    if ((m + i) & 1)
      cur = 1ll * cur * (t - i + 1) % mod;
    else
      cur = 1ll * cur * t % mod;
    cur = 1ll * cur * inv[i] % mod;
    if (i & 1)
      b[i] = ((i / 2) & 1 ? -1 : 1) * cur;
    else
      a[i] = ((i / 2) & 1 ? 1 : -1) * cur;
    a[i] = (a[i] + mod) % mod;
    b[i] = (b[i] + mod) % mod;
  }
  rev(a);
  vector<int> c = b * Inv(a);
  rev(c);
  vector<int> f = Ln(Inv(a));
  vector<int> g = Ln(Inv(c));
  print(1ll * n * (f[n] + g[n]) % mod, '\n');
  return 0;
}

```