#include <bits/stdc++.h>
template <typename _Tp>
void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
const int max_len = 1 << 17, N = max_len + 5, mod = 998244353;
template <typename _Tp1, typename _Tp2>
inline void add(_Tp1 &a, _Tp2 b) {
  (a += b) >= mod && (a -= mod);
}
template <typename _Tp1, typename _Tp2>
inline void sub(_Tp1 &a, _Tp2 b) {
  (a -= b) < 0 && (a += mod);
}
long long ksm(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return res;
}
void print(const std::vector<int> &a) {
  for (auto it : a) printf("%d ", it);
  printf("\n");
}
inline std::vector<int> operator<<(std::vector<int> a, unsigned int b) {
  return a.insert(a.begin(), b, 0), a;
}
inline std::vector<int> operator<<=(std::vector<int> &a, unsigned int b) {
  return a.insert(a.begin(), b, 0), a;
}
inline std::vector<int> operator>>(const std::vector<int> &a, unsigned int b) {
  return b >= a.size() ? std::vector<int>()
                       : std::vector<int>{a.begin() + b, a.end()};
}
inline std::vector<int> operator>>=(std::vector<int> &a, unsigned int b) {
  return a = b >= a.size() ? std::vector<int>()
                           : std::vector<int>{a.begin() + b, a.end()};
}
std::vector<int> operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (unsigned int i = 0; i < b.size(); ++i) add(a[i], b[i]);
  return a;
}
inline std::vector<int> operator+(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp += b;
  return tmp;
}
std::vector<int> operator-=(std::vector<int> &a, const std::vector<int> &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (unsigned int i = 0; i < b.size(); ++i) sub(a[i], b[i]);
  return a;
}
inline std::vector<int> operator-(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp -= b;
  return tmp;
}
unsigned long long Omgs[N];
int r[N];
const unsigned long long Omg = ksm(3, (mod - 1) / max_len);
int getlen(int len) {
  int limit = 1;
  while (limit < len) limit <<= 1;
  for (int i = 0; i < limit; ++i)
    r[i] = (r[i >> 1] >> 1) | (i & 1 ? limit >> 1 : 0);
  return limit;
}
void setup() {
  Omgs[max_len >> 1] = 1;
  for (int i = (max_len >> 1) + 1; i < max_len; ++i)
    Omgs[i] = Omgs[i - 1] * Omg % mod;
  for (int i = (max_len >> 1) - 1; i > 0; --i) Omgs[i] = Omgs[i << 1];
}
void dft(unsigned long long *A, int limit) {
  for (int i = 0; i < limit; ++i)
    if (i < r[i]) std::swap(A[i], A[r[i]]);
  for (int len = 1; len < limit; len <<= 1) {
    if (len == 262144)
      for (int i = 0; i < limit; ++i) A[i] %= mod;
    for (int i = 0; i < limit; i += len << 1) {
      unsigned long long *p = A + i, *q = A + i + len, *w = Omgs + len;
      for (int _ = 0; _ < len; ++_, ++p, ++q, ++w) {
        unsigned long long tmp = *q * *w % mod;
        *q = *p + mod - tmp, *p += tmp;
      }
    }
  }
  for (int i = 0; i < limit; ++i) A[i] %= mod;
}
void idft(unsigned long long *A, int limit) {
  std::reverse(A + 1, A + limit), dft(A, limit);
  unsigned long long inv = mod - (mod - 1) / limit;
  for (int i = 0; i < limit; ++i) A[i] = inv * A[i] % mod;
}
unsigned long long _f[N], _g[N], _tp[N];
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b) {
  unsigned int len = a.size() + b.size() - 1;
  if (a.size() <= 64u || b.size() <= 64u) {
    memset(_tp, 0, len << 3);
    unsigned int r = 0;
    for (unsigned int i = 0; i < a.size(); ++i) {
      for (unsigned int j = 0; j < b.size(); ++j)
        _tp[i + j] += 1ULL * a[i] * b[j];
      if (++r == 18) {
        r = 0;
        for (unsigned int j = i - 17; j < i + b.size(); ++j) _tp[j] %= mod;
      }
    }
    if (r)
      for (unsigned int j = 0; j < len; ++j) _tp[j] %= mod;
    std::vector<int> c(len);
    for (unsigned int i = 0; i < len; ++i) c[i] = _tp[i];
    return c;
  }
  int limit = getlen(len);
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  memset(_g, 0, limit << 3);
  for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
  dft(_f, limit), dft(_g, limit);
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b,
                     unsigned int len, bool need = true) {
  if (a.size() <= 64u || b.size() <= 64u) {
    memset(_tp, 0, len << 3);
    unsigned int r = 0;
    for (unsigned int i = 0; i < a.size(); ++i) {
      for (unsigned int j = 0; j < b.size() && i + j < len; ++j)
        _tp[i + j] += 1ULL * a[i] * b[j];
      if (++r == 18) {
        r = 0;
        for (unsigned int j = i - 17; j < len && j < i + b.size(); ++j)
          _tp[j] %= mod;
      }
    }
    if (r)
      for (unsigned int j = 0; j < len; ++j) _tp[j] %= mod;
    std::vector<int> c(len);
    for (unsigned int i = 0; i < len; ++i) c[i] = _tp[i];
    return c;
  }
  int limit = getlen(len);
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  dft(_f, limit);
  if (need) {
    memset(_g, 0, limit << 3);
    for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
    dft(_g, limit);
  }
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
inline std::vector<int> operator*=(std::vector<int> &a,
                                   const std::vector<int> &b) {
  return a = a * b;
}
template <typename _Tp>
inline std::vector<int> operator*=(std::vector<int> &a, const _Tp &b) {
  for (auto &&it : a) it = 1ULL * it * b % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator*(std::vector<int> a, const _Tp &b) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator*(const _Tp &b, std::vector<int> a) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator/=(std::vector<int> &a, const _Tp &b) {
  unsigned long long inv = ksm(b);
  for (auto &&it : a) it = 1ULL * it * inv % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator/(std::vector<int> a, const _Tp &b) {
  return a /= b;
}
std::vector<int> Inv(const std::vector<int> &F) {
  if (F.size() == 1u) return {(int)ksm(F[0])};
  unsigned int len = F.size(), l = (len + 1) >> 1;
  std::vector<int> H(Inv({F.begin(), F.begin() + l})), tmp(mul(F, H, len)),
      ans(H);
  memset(tmp.data(), 0, l << 2), tmp = mul(tmp, H, len, false), ans.resize(len);
  for (unsigned int i = l; i < len; ++i) tmp[i] && (ans[i] = mod - tmp[i]);
  return ans;
}
int n, ans;
std::vector<int> solve(int m) {
  if (!m) {
    std::vector<int> f(n + 1);
    f[0] = 1;
    return f;
  }
  std::vector<int> tmp = solve(m / 2), A(n + 1), B(n + 1);
  for (int i = 0; i <= n; ++i) (i % 2 ? A : B)[i] = tmp[i];
  A[1] = (m + 1) / 2;
  std::vector<int> C = B * B, D = Inv(std::vector<int>{1} - A);
  C.resize(n + 1);
  C *= D, C.resize(n + 1);
  C += A;
  if (n % 2 == 0)
    add(ans, ans);
  else
    ans = 0;
  for (int i = 1; i <= n; i += 2)
    add(ans, 1LL * A[i] * D[n - i] % mod * i % mod);
  return C;
}
int main() {
  setup();
  int m;
  read(n, m);
  solve(m);
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
template <typename _Tp>
void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
const int max_len = 1 << 17, N = max_len + 5, mod = 998244353;
template <typename _Tp1, typename _Tp2>
inline void add(_Tp1 &a, _Tp2 b) {
  (a += b) >= mod && (a -= mod);
}
template <typename _Tp1, typename _Tp2>
inline void sub(_Tp1 &a, _Tp2 b) {
  (a -= b) < 0 && (a += mod);
}
long long ksm(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return res;
}
void print(const std::vector<int> &a) {
  for (auto it : a) printf("%d ", it);
  printf("\n");
}
inline std::vector<int> operator<<(std::vector<int> a, unsigned int b) {
  return a.insert(a.begin(), b, 0), a;
}
inline std::vector<int> operator<<=(std::vector<int> &a, unsigned int b) {
  return a.insert(a.begin(), b, 0), a;
}
inline std::vector<int> operator>>(const std::vector<int> &a, unsigned int b) {
  return b >= a.size() ? std::vector<int>()
                       : std::vector<int>{a.begin() + b, a.end()};
}
inline std::vector<int> operator>>=(std::vector<int> &a, unsigned int b) {
  return a = b >= a.size() ? std::vector<int>()
                           : std::vector<int>{a.begin() + b, a.end()};
}
std::vector<int> operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (unsigned int i = 0; i < b.size(); ++i) add(a[i], b[i]);
  return a;
}
inline std::vector<int> operator+(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp += b;
  return tmp;
}
std::vector<int> operator-=(std::vector<int> &a, const std::vector<int> &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (unsigned int i = 0; i < b.size(); ++i) sub(a[i], b[i]);
  return a;
}
inline std::vector<int> operator-(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp -= b;
  return tmp;
}
unsigned long long Omgs[N];
int r[N];
const unsigned long long Omg = ksm(3, (mod - 1) / max_len);
int getlen(int len) {
  int limit = 1;
  while (limit < len) limit <<= 1;
  for (int i = 0; i < limit; ++i)
    r[i] = (r[i >> 1] >> 1) | (i & 1 ? limit >> 1 : 0);
  return limit;
}
void setup() {
  Omgs[max_len >> 1] = 1;
  for (int i = (max_len >> 1) + 1; i < max_len; ++i)
    Omgs[i] = Omgs[i - 1] * Omg % mod;
  for (int i = (max_len >> 1) - 1; i > 0; --i) Omgs[i] = Omgs[i << 1];
}
void dft(unsigned long long *A, int limit) {
  for (int i = 0; i < limit; ++i)
    if (i < r[i]) std::swap(A[i], A[r[i]]);
  for (int len = 1; len < limit; len <<= 1) {
    if (len == 262144)
      for (int i = 0; i < limit; ++i) A[i] %= mod;
    for (int i = 0; i < limit; i += len << 1) {
      unsigned long long *p = A + i, *q = A + i + len, *w = Omgs + len;
      for (int _ = 0; _ < len; ++_, ++p, ++q, ++w) {
        unsigned long long tmp = *q * *w % mod;
        *q = *p + mod - tmp, *p += tmp;
      }
    }
  }
  for (int i = 0; i < limit; ++i) A[i] %= mod;
}
void idft(unsigned long long *A, int limit) {
  std::reverse(A + 1, A + limit), dft(A, limit);
  unsigned long long inv = mod - (mod - 1) / limit;
  for (int i = 0; i < limit; ++i) A[i] = inv * A[i] % mod;
}
unsigned long long _f[N], _g[N], _tp[N];
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b) {
  unsigned int len = a.size() + b.size() - 1;
  if (a.size() <= 64u || b.size() <= 64u) {
    memset(_tp, 0, len << 3);
    unsigned int r = 0;
    for (unsigned int i = 0; i < a.size(); ++i) {
      for (unsigned int j = 0; j < b.size(); ++j)
        _tp[i + j] += 1ULL * a[i] * b[j];
      if (++r == 18) {
        r = 0;
        for (unsigned int j = i - 17; j < i + b.size(); ++j) _tp[j] %= mod;
      }
    }
    if (r)
      for (unsigned int j = 0; j < len; ++j) _tp[j] %= mod;
    std::vector<int> c(len);
    for (unsigned int i = 0; i < len; ++i) c[i] = _tp[i];
    return c;
  }
  int limit = getlen(len);
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  memset(_g, 0, limit << 3);
  for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
  dft(_f, limit), dft(_g, limit);
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b,
                     unsigned int len, bool need = true) {
  if (a.size() <= 64u || b.size() <= 64u) {
    memset(_tp, 0, len << 3);
    unsigned int r = 0;
    for (unsigned int i = 0; i < a.size(); ++i) {
      for (unsigned int j = 0; j < b.size() && i + j < len; ++j)
        _tp[i + j] += 1ULL * a[i] * b[j];
      if (++r == 18) {
        r = 0;
        for (unsigned int j = i - 17; j < len && j < i + b.size(); ++j)
          _tp[j] %= mod;
      }
    }
    if (r)
      for (unsigned int j = 0; j < len; ++j) _tp[j] %= mod;
    std::vector<int> c(len);
    for (unsigned int i = 0; i < len; ++i) c[i] = _tp[i];
    return c;
  }
  int limit = getlen(len);
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  dft(_f, limit);
  if (need) {
    memset(_g, 0, limit << 3);
    for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
    dft(_g, limit);
  }
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
inline std::vector<int> operator*=(std::vector<int> &a,
                                   const std::vector<int> &b) {
  return a = a * b;
}
template <typename _Tp>
inline std::vector<int> operator*=(std::vector<int> &a, const _Tp &b) {
  for (auto &&it : a) it = 1ULL * it * b % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator*(std::vector<int> a, const _Tp &b) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator*(const _Tp &b, std::vector<int> a) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator/=(std::vector<int> &a, const _Tp &b) {
  unsigned long long inv = ksm(b);
  for (auto &&it : a) it = 1ULL * it * inv % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator/(std::vector<int> a, const _Tp &b) {
  return a /= b;
}
std::vector<int> Inv(const std::vector<int> &F) {
  if (F.size() == 1u) return {(int)ksm(F[0])};
  unsigned int len = F.size(), l = (len + 1) >> 1;
  std::vector<int> H(Inv({F.begin(), F.begin() + l})), tmp(mul(F, H, len)),
      ans(H);
  memset(tmp.data(), 0, l << 2), tmp = mul(tmp, H, len, false), ans.resize(len);
  for (unsigned int i = l; i < len; ++i) tmp[i] && (ans[i] = mod - tmp[i]);
  return ans;
}
int n, ans;
std::vector<int> solve(int m) {
  if (!m) {
    std::vector<int> f(n + 1);
    f[0] = 1;
    return f;
  }
  std::vector<int> tmp = solve(m / 2), A(n + 1), B(n + 1);
  for (int i = 0; i <= n; ++i) (i % 2 ? A : B)[i] = tmp[i];
  A[1] = (m + 1) / 2;
  std::vector<int> C = B * B, D = Inv(std::vector<int>{1} - A);
  C.resize(n + 1);
  C *= D, C.resize(n + 1);
  C += A;
  if (n % 2 == 0)
    add(ans, ans);
  else
    ans = 0;
  for (int i = 1; i <= n; i += 2)
    add(ans, 1LL * A[i] * D[n - i] % mod * i % mod);
  return C;
}
int main() {
  setup();
  int m;
  read(n, m);
  solve(m);
  printf("%d\n", ans);
  return 0;
}

```