#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 19;
const int MOD = 998244353;
const int g = 3;
int W[N];
int n, m;
int qpow(int a, int k) {
  int res = 1, t = a;
  while (k) {
    if (k & 1) {
      res = (long long)res * t % MOD;
    }
    t = (long long)t * t % MOD;
    k >>= 1;
  }
  return res;
}
void ntt(vector<int> &A, int ty) {
  for (int i = 0; i < (int)A.size(); ++i) {
    int j = 0, k = i, m = 1;
    while (m < (int)A.size()) {
      m <<= 1;
      j = (j << 1) | (k & 1);
      k >>= 1;
    }
    if (i < j) {
      swap(A[i], A[j]);
    }
  }
  W[0] = 1;
  for (int m = 1; m < (int)A.size(); m <<= 1) {
    int t = qpow(g, MOD - 1 + ty * (MOD - 1) / (m << 1));
    for (int i = 1; i < m; ++i) {
      W[i] = 1LL * W[i - 1] * t % MOD;
    }
    for (int k = 0; k < (int)A.size(); k += m << 1) {
      for (int i = k; i < k + m; ++i) {
        int t1 = A[i];
        long long t2 = (long long)A[i + m] * W[i - k] % MOD;
        A[i] = t1 + t2;
        A[i] -= A[i] > MOD ? MOD : 0;
        A[i + m] = t1 - t2;
        A[i + m] += A[i + m] < 0 ? MOD : 0;
      }
    }
  }
  if (ty == 1) {
    return;
  }
  int t = qpow((int)A.size(), MOD - 2);
  for (int i = 0; i < (int)A.size(); ++i) {
    A[i] = (long long)A[i] * t % MOD;
  }
}
int getsz(int n) {
  if (n ^ (n & -n)) n <<= 1;
  while (n ^ (n & -n)) n ^= n & -n;
  return n;
}
void poly_resz(vector<int> &a) {
  int n = getsz(a.size());
  a.resize(n, 0);
}
vector<int> poly_mul(vector<int> &a, vector<int> &b) {
  int len = getsz(a.size() + b.size() - 1);
  vector<int> c(len, 0);
  vector<int> d(len, 0);
  copy(a.begin(), a.end(), c.begin());
  copy(b.begin(), b.end(), d.begin());
  ntt(c, 1);
  ntt(d, 1);
  for (int i = 0; i < len; ++i) {
    c[i] = (long long)c[i] * d[i] % MOD;
  }
  ntt(c, -1);
  return c;
}
void poly_mul_inplace(vector<int> &a, vector<int> &b) {
  int len = a.size() + b.size() - 1;
  if (len ^ (len & -len)) len <<= 1;
  while (len ^ (len & -len)) len ^= len & -len;
  a.resize(len, 0);
  b.resize(len, 0);
  ntt(a, 1);
  ntt(b, 1);
  for (int i = 0; i < len; ++i) {
    a[i] = (long long)a[i] * b[i] % MOD;
  }
  ntt(a, -1);
}
vector<int> c(N), d(N);
void poly_inv_inplace(vector<int> &f, vector<int> &finv) {
  poly_resz(f);
  int n = f.size();
  finv.assign(n, 0);
  finv[0] = qpow(f[0], MOD - 2);
  for (int m = 2; m <= n; m <<= 1) {
    c.assign(m << 1, 0);
    d.assign(m << 1, 0);
    copy(finv.begin(), finv.begin() + m / 2, c.begin());
    copy(f.begin(), f.begin() + m, d.begin());
    ntt(d, 1);
    ntt(c, 1);
    for (int i = 0; i < (m << 1); ++i) {
      d[i] = (long long)d[i] * c[i] % MOD * c[i] % MOD;
    }
    ntt(d, -1);
    for (int i = 0; i < m; ++i) {
      finv[i] = (2LL * finv[i] - d[i] + MOD) % MOD;
    }
  }
}
void rev_inplace(vector<int> &f) {
  f[0] = (1 - f[0] + MOD) % MOD;
  for (int i = 1; i < f.size(); ++i) {
    f[i] = (MOD - f[i]) % MOD;
  }
}
int inv[N];
vector<int> F(N + 1), G(N + 1), Finv(N + 1), P(N + 1), Q(N + 1);
int solve() {
  if (n & 1) {
    F.assign(n + 1, 0);
    G.assign(n + 1, 0);
    P.assign(n + 1, 0);
    Q.assign(n + 1, 0);
    int cl = m / 2;
    long long h = 1;
    for (int i = 1; i <= n; ++i) {
      int k = i / 2;
      if (i & 1)
        h = 1LL * h * ((cl - k + MOD) % MOD) % MOD;
      else
        h = 1LL * h * (cl + k) % MOD;
      h = 1LL * h * inv[i] % MOD;
      if (i & 1)
        Q[i] = h;
      else
        P[i] = (MOD - h);
    }
    rev_inplace(P);
    poly_inv_inplace(P, Finv);
    poly_mul_inplace(Q, Finv);
    for (int i = 1; i <= n; i += 2) {
      if (i / 2 % 2) Q[i] = MOD - Q[i];
    }
    if (m & 1) {
      Q[1] = (Q[1] + 1LL) % MOD;
    }
    for (int i = 1; i <= n; i += 2) {
      F[i] = Q[i] % MOD;
      G[i] = 1LL * i * F[i] % MOD;
    }
    rev_inplace(F);
    poly_inv_inplace(F, Finv);
    poly_mul_inplace(G, Finv);
    return G[n];
  } else {
    F.assign(n + 1, 0);
    G.assign(n + 1, 0);
    long long c = 1;
    for (int i = 2; i <= n; i += 2) {
      int k = i / 2;
      long long h = 1LL * (m + k) * (m - k + 1) % MOD;
      c = c * h % MOD * inv[2 * k] % MOD * inv[2 * k - 1] % MOD;
      F[i] = MOD - c;
      G[i] = 1LL * k * F[i] % MOD;
    }
    rev_inplace(F);
    poly_inv_inplace(F, Finv);
    poly_mul_inplace(Finv, G);
    return (Finv[n] * (n / 2 % 2 ? -1LL : 1LL) + MOD) % MOD;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = qpow(i, MOD - 2);
  }
  cout << solve() << endl;
  return 0;
}

### Prompt

Create a solution in Cpp for 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 N = 1 << 19;
const int MOD = 998244353;
const int g = 3;
int W[N];
int n, m;
int qpow(int a, int k) {
  int res = 1, t = a;
  while (k) {
    if (k & 1) {
      res = (long long)res * t % MOD;
    }
    t = (long long)t * t % MOD;
    k >>= 1;
  }
  return res;
}
void ntt(vector<int> &A, int ty) {
  for (int i = 0; i < (int)A.size(); ++i) {
    int j = 0, k = i, m = 1;
    while (m < (int)A.size()) {
      m <<= 1;
      j = (j << 1) | (k & 1);
      k >>= 1;
    }
    if (i < j) {
      swap(A[i], A[j]);
    }
  }
  W[0] = 1;
  for (int m = 1; m < (int)A.size(); m <<= 1) {
    int t = qpow(g, MOD - 1 + ty * (MOD - 1) / (m << 1));
    for (int i = 1; i < m; ++i) {
      W[i] = 1LL * W[i - 1] * t % MOD;
    }
    for (int k = 0; k < (int)A.size(); k += m << 1) {
      for (int i = k; i < k + m; ++i) {
        int t1 = A[i];
        long long t2 = (long long)A[i + m] * W[i - k] % MOD;
        A[i] = t1 + t2;
        A[i] -= A[i] > MOD ? MOD : 0;
        A[i + m] = t1 - t2;
        A[i + m] += A[i + m] < 0 ? MOD : 0;
      }
    }
  }
  if (ty == 1) {
    return;
  }
  int t = qpow((int)A.size(), MOD - 2);
  for (int i = 0; i < (int)A.size(); ++i) {
    A[i] = (long long)A[i] * t % MOD;
  }
}
int getsz(int n) {
  if (n ^ (n & -n)) n <<= 1;
  while (n ^ (n & -n)) n ^= n & -n;
  return n;
}
void poly_resz(vector<int> &a) {
  int n = getsz(a.size());
  a.resize(n, 0);
}
vector<int> poly_mul(vector<int> &a, vector<int> &b) {
  int len = getsz(a.size() + b.size() - 1);
  vector<int> c(len, 0);
  vector<int> d(len, 0);
  copy(a.begin(), a.end(), c.begin());
  copy(b.begin(), b.end(), d.begin());
  ntt(c, 1);
  ntt(d, 1);
  for (int i = 0; i < len; ++i) {
    c[i] = (long long)c[i] * d[i] % MOD;
  }
  ntt(c, -1);
  return c;
}
void poly_mul_inplace(vector<int> &a, vector<int> &b) {
  int len = a.size() + b.size() - 1;
  if (len ^ (len & -len)) len <<= 1;
  while (len ^ (len & -len)) len ^= len & -len;
  a.resize(len, 0);
  b.resize(len, 0);
  ntt(a, 1);
  ntt(b, 1);
  for (int i = 0; i < len; ++i) {
    a[i] = (long long)a[i] * b[i] % MOD;
  }
  ntt(a, -1);
}
vector<int> c(N), d(N);
void poly_inv_inplace(vector<int> &f, vector<int> &finv) {
  poly_resz(f);
  int n = f.size();
  finv.assign(n, 0);
  finv[0] = qpow(f[0], MOD - 2);
  for (int m = 2; m <= n; m <<= 1) {
    c.assign(m << 1, 0);
    d.assign(m << 1, 0);
    copy(finv.begin(), finv.begin() + m / 2, c.begin());
    copy(f.begin(), f.begin() + m, d.begin());
    ntt(d, 1);
    ntt(c, 1);
    for (int i = 0; i < (m << 1); ++i) {
      d[i] = (long long)d[i] * c[i] % MOD * c[i] % MOD;
    }
    ntt(d, -1);
    for (int i = 0; i < m; ++i) {
      finv[i] = (2LL * finv[i] - d[i] + MOD) % MOD;
    }
  }
}
void rev_inplace(vector<int> &f) {
  f[0] = (1 - f[0] + MOD) % MOD;
  for (int i = 1; i < f.size(); ++i) {
    f[i] = (MOD - f[i]) % MOD;
  }
}
int inv[N];
vector<int> F(N + 1), G(N + 1), Finv(N + 1), P(N + 1), Q(N + 1);
int solve() {
  if (n & 1) {
    F.assign(n + 1, 0);
    G.assign(n + 1, 0);
    P.assign(n + 1, 0);
    Q.assign(n + 1, 0);
    int cl = m / 2;
    long long h = 1;
    for (int i = 1; i <= n; ++i) {
      int k = i / 2;
      if (i & 1)
        h = 1LL * h * ((cl - k + MOD) % MOD) % MOD;
      else
        h = 1LL * h * (cl + k) % MOD;
      h = 1LL * h * inv[i] % MOD;
      if (i & 1)
        Q[i] = h;
      else
        P[i] = (MOD - h);
    }
    rev_inplace(P);
    poly_inv_inplace(P, Finv);
    poly_mul_inplace(Q, Finv);
    for (int i = 1; i <= n; i += 2) {
      if (i / 2 % 2) Q[i] = MOD - Q[i];
    }
    if (m & 1) {
      Q[1] = (Q[1] + 1LL) % MOD;
    }
    for (int i = 1; i <= n; i += 2) {
      F[i] = Q[i] % MOD;
      G[i] = 1LL * i * F[i] % MOD;
    }
    rev_inplace(F);
    poly_inv_inplace(F, Finv);
    poly_mul_inplace(G, Finv);
    return G[n];
  } else {
    F.assign(n + 1, 0);
    G.assign(n + 1, 0);
    long long c = 1;
    for (int i = 2; i <= n; i += 2) {
      int k = i / 2;
      long long h = 1LL * (m + k) * (m - k + 1) % MOD;
      c = c * h % MOD * inv[2 * k] % MOD * inv[2 * k - 1] % MOD;
      F[i] = MOD - c;
      G[i] = 1LL * k * F[i] % MOD;
    }
    rev_inplace(F);
    poly_inv_inplace(F, Finv);
    poly_mul_inplace(Finv, G);
    return (Finv[n] * (n / 2 % 2 ? -1LL : 1LL) + MOD) % MOD;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = qpow(i, MOD - 2);
  }
  cout << solve() << endl;
  return 0;
}

```