#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
namespace mypoly {
const int MOD = 998244353;
const int g = 3;
int qmul(int x, int y) { return 1ll * x * y - 1ll * x * y / MOD * MOD; }
int qadd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
int G[21][(1 << 20) + 1], R[21][(1 << 20) + 1], inver[(1 << 20) + 1];
int quick(int A, int B) {
  int res = 1;
  while (B) {
    if (B & 1) res = qmul(res, A);
    A = qmul(A, A);
    B >>= 1;
  }
  return res;
}
int inv(int x) { return quick(x, MOD - 2); }
struct POLY {
  int len;
  int rev[1 << 20];
  POLY() {
    for (int i = 1; i <= (1 << 20); ++i) inver[i] = inv(i);
    for (int i = 1; i <= 20; ++i) {
      G[i][0] = 1;
      R[i][0] = 1;
      int tmp2 = inv(quick(g, (MOD - 1) >> i));
      int tmp = quick(g, (MOD - 1) >> i);
      for (int j = 1; j <= (1 << i); ++j) {
        G[i][j] = qmul(G[i][j - 1], tmp);
        R[i][j] = qmul(R[i][j - 1], tmp2);
      }
    }
  }
  void butterfly(vector<int>& v) {
    for (int i = 0; i < len; ++i) {
      rev[i] = rev[i >> 1] >> 1;
      if (i & 1) rev[i] |= len >> 1;
    }
    for (int i = 0; i < len; ++i)
      if (rev[i] > i) swap(v[i], v[rev[i]]);
  }
  vector<int> ntt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(B, G[lg][k]);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  vector<int> intt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(R[lg][k], B);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  void getlen(int x) {
    len = 1;
    while (len < x) {
      len <<= 1;
    }
  }
  vector<int> mul(vector<int> A, vector<int> B) {
    if (A.size() + B.size() <= 25) {
      vector<int> ret(A.size() + B.size() - 1);
      for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < B.size(); ++j)
          ret[i + j] = qadd(ret[i + j], qmul(A[i], B[j]));
      return ret;
    }
    getlen(A.size() + B.size());
    A.resize(len);
    B.resize(len);
    A = ntt(A);
    B = ntt(B);
    for (int i = 0; i < len; ++i) A[i] = qmul(A[i], B[i]);
    A = intt(A);
    int iv = inver[len];
    for (int i = 0; i < len; ++i) {
      A[i] = qmul(A[i], iv);
    }
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
  }
  vector<int> inverse(vector<int> A, int n) {
    vector<int> ret(n);
    if (n == 1) {
      ret[0] = quick(A[0], MOD - 2);
    } else {
      vector<int> oth = inverse(A, (n + 1) >> 1);
      ret = oth;
      ret.resize(n);
      for (int i = 0; i < n; ++i) ret[i] = (ret[i] + ret[i]) % MOD;
      getlen((oth.size() << 1) + A.size());
      oth.resize(len);
      A.resize(len);
      oth = ntt(oth);
      A = ntt(A);
      for (int i = 0; i < len; ++i) oth[i] = qmul(qmul(oth[i], oth[i]), A[i]);
      oth = intt(oth);
      oth.resize(n);
      int iv = inver[len];
      for (int i = 0; i < n; ++i) {
        oth[i] = qmul(oth[i], iv);
      }
      for (int i = 0; i < n; ++i) ret[i] = qadd(ret[i], MOD - oth[i]);
    }
    return ret;
  }
} poly;
vector<int> operator*(vector<int> A, vector<int> B) { return poly.mul(A, B); }
vector<int> operator+(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], B[i]);
  return A;
}
vector<int> operator-(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], MOD - B[i]);
  return A;
}
vector<int> operator/(vector<int> A, vector<int> B) {
  return A * poly.inverse(B, A.size() - B.size() + 1);
}
vector<int> operator%(vector<int> A, vector<int> B) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  while (B.size() != 1 && B.back() == 0) B.pop_back();
  if (B.size() > A.size()) return A;
  vector<int> rem, mod;
  int n, m;
  n = A.size() - 1;
  m = B.size() - 1;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem = A / B;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem.resize(n - m + 1);
  reverse(rem.begin(), rem.end());
  mod = A - rem * B;
  mod.resize(m);
  return mod;
}
vector<int> der(vector<int> A) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  vector<int> ret(A.size() - 1);
  for (int i = 0; i < ret.size(); ++i) ret[i] = 1ll * (i + 1) * A[i + 1] % MOD;
  if (ret.empty()) return vector<int>(1, 0);
  return ret;
}
class MC {
  vector<vector<int> > RAM;
  vector<vector<int> > SIN;
  vector<int> Lc;
  vector<int> Rc;
  vector<int> ret;
  vector<int> x_;
  void fendge1(int l, int r, int& cnt) {
    if (l == r - 1) {
      Lc.push_back(0);
      Rc.push_back(0);
      RAM.push_back(SIN[l]);
      return;
    }
    RAM.push_back(vector<int>(0));
    Lc.push_back(0);
    Rc.push_back(0);
    int now = cnt;
    int mid = (l + r) >> 1;
    int L = ++cnt;
    fendge1(l, mid, cnt);
    int R = ++cnt;
    fendge1(mid, r, cnt);
    Lc[now] = L;
    Rc[now] = R;
    RAM[now] = RAM[L] * RAM[R];
  }
  void fendge2(int l, int r, int cnt, vector<int> p) {
    p = p % RAM[cnt];
    if (r - l <= 300) {
      for (int i = l; i <= r - 1; ++i) {
        int T = 1;
        for (int j = 0; j < p.size(); ++j) {
          ret[i] = qadd(ret[i], qmul(T, p[j]));
          T = qmul(T, x_[i]);
        }
      }
      return;
    }
    int mid = (l + r) >> 1;
    fendge2(l, mid, Lc[cnt], p);
    fendge2(mid, r, Rc[cnt], p);
  }

 public:
  vector<int> init(vector<int> p, vector<int> x) {
    x_ = x;
    Lc.clear();
    Rc.clear();
    RAM.clear();
    SIN.clear();
    ret.clear();
    ret.resize(x.size());
    for (int i = 0; i < x.size(); ++i) {
      SIN.push_back(vector<int>{(MOD - x[i]), 1});
    }
    int cnt = 0;
    fendge1(0, x.size(), cnt);
    fendge2(0, x.size(), 0, p);
    return ret;
  }
} mc;
vector<int> multiple_calculation(vector<int> p, vector<int> x) {
  return mc.init(p, x);
}
class ITP {
  vector<int> u;
  vector<int> v;
  vector<int> fm;
  vector<int> fendge(int l, int r) {
    if (l == r - 1) {
      return vector<int>{(MOD - u[l]), 1};
    }
    int mid = (l + r) >> 1;
    return fendge(l, mid) * fendge(mid, r);
  }
  pair<vector<int>, vector<int> > fendge2(int l, int r) {
    if (l == r - 1) {
      return {vector<int>{(MOD - u[l]), 1}, vector<int>{fm[l]}};
    }
    int mid = (l + r) >> 1;
    pair<vector<int>, vector<int> > L, R;
    L = fendge2(l, mid);
    R = fendge2(mid, r);
    return {L.first * R.first, L.first * R.second + R.first * L.second};
  }

 public:
  vector<int> solve(vector<pair<int, int> > x) {
    u.clear();
    v.clear();
    int n = x.size();
    for (auto it : x) u.push_back(it.first), v.push_back(it.second);
    vector<int> g = fendge(0, u.size());
    fm = multiple_calculation(der(g), u);
    for (int i = 0; i < n; ++i) {
      fm[i] = qmul(v[i], inv(fm[i]));
    }
    return fendge2(0, n).second;
  }
} itp;
vector<int> interpolation(vector<pair<int, int> > x) { return itp.solve(x); }
}  // namespace mypoly
using namespace mypoly;
const int MAXN = 5e4 + 1;
void add(int& A, int B) {
  A += B;
  if (A >= MOD) A -= MOD;
}
int n;
pair<int, vector<int> > solve(int n, int m) {
  if (m == 1) {
    vector<int> ret(n + 1, 1);
    ret[0] = 0;
    return make_pair(1, ret);
  }
  pair<int, vector<int> > small = solve(n, m / 2);
  int smallcyc = small.first;
  vector<int> smallline = small.second;
  smallline[1] = (m + 1) / 2;
  int anscyc = 0;
  if (n % 2 == 0) add(anscyc, 2ll * smallcyc % MOD);
  vector<int> odd(n + 1, 0);
  for (int i = 1; i <= n; ++i)
    if (i & 1) odd[i] = smallline[i];
  vector<int> orodd = odd;
  odd[0] = 1;
  for (int i = 1; i <= n; ++i) odd[i] = (MOD - odd[i]) % MOD;
  odd = poly.inverse(odd, n + 1);
  for (int i = 1; i <= n; ++i) orodd[i] = 1ll * i * orodd[i] % MOD;
  add(anscyc, (odd * orodd)[n]);
  vector<int> ansline(n + 1, 0);
  vector<int> even(n + 1, 0);
  for (int i = 1; i <= n; ++i)
    if (i % 2 == 0) even[i] = smallline[i];
  for (int i = 1; i <= n; ++i) add(ansline[i], odd[i]);
  vector<int> tmp = even * odd;
  for (int i = 1; i <= n; ++i) add(ansline[i], 2ll * tmp[i] % MOD);
  tmp = even * tmp;
  for (int i = 1; i <= n; ++i) add(ansline[i], tmp[i]);
  for (int i = 1; i <= n; ++i)
    if (i & 1) add(ansline[i], smallline[i]);
  return make_pair(anscyc, ansline);
}
int main() {
  int m;
  cin >> n >> m;
  cout << solve(n, m).first << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 INF = 0x3f3f3f3f;
namespace mypoly {
const int MOD = 998244353;
const int g = 3;
int qmul(int x, int y) { return 1ll * x * y - 1ll * x * y / MOD * MOD; }
int qadd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
int G[21][(1 << 20) + 1], R[21][(1 << 20) + 1], inver[(1 << 20) + 1];
int quick(int A, int B) {
  int res = 1;
  while (B) {
    if (B & 1) res = qmul(res, A);
    A = qmul(A, A);
    B >>= 1;
  }
  return res;
}
int inv(int x) { return quick(x, MOD - 2); }
struct POLY {
  int len;
  int rev[1 << 20];
  POLY() {
    for (int i = 1; i <= (1 << 20); ++i) inver[i] = inv(i);
    for (int i = 1; i <= 20; ++i) {
      G[i][0] = 1;
      R[i][0] = 1;
      int tmp2 = inv(quick(g, (MOD - 1) >> i));
      int tmp = quick(g, (MOD - 1) >> i);
      for (int j = 1; j <= (1 << i); ++j) {
        G[i][j] = qmul(G[i][j - 1], tmp);
        R[i][j] = qmul(R[i][j - 1], tmp2);
      }
    }
  }
  void butterfly(vector<int>& v) {
    for (int i = 0; i < len; ++i) {
      rev[i] = rev[i >> 1] >> 1;
      if (i & 1) rev[i] |= len >> 1;
    }
    for (int i = 0; i < len; ++i)
      if (rev[i] > i) swap(v[i], v[rev[i]]);
  }
  vector<int> ntt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(B, G[lg][k]);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  vector<int> intt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(R[lg][k], B);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  void getlen(int x) {
    len = 1;
    while (len < x) {
      len <<= 1;
    }
  }
  vector<int> mul(vector<int> A, vector<int> B) {
    if (A.size() + B.size() <= 25) {
      vector<int> ret(A.size() + B.size() - 1);
      for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < B.size(); ++j)
          ret[i + j] = qadd(ret[i + j], qmul(A[i], B[j]));
      return ret;
    }
    getlen(A.size() + B.size());
    A.resize(len);
    B.resize(len);
    A = ntt(A);
    B = ntt(B);
    for (int i = 0; i < len; ++i) A[i] = qmul(A[i], B[i]);
    A = intt(A);
    int iv = inver[len];
    for (int i = 0; i < len; ++i) {
      A[i] = qmul(A[i], iv);
    }
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
  }
  vector<int> inverse(vector<int> A, int n) {
    vector<int> ret(n);
    if (n == 1) {
      ret[0] = quick(A[0], MOD - 2);
    } else {
      vector<int> oth = inverse(A, (n + 1) >> 1);
      ret = oth;
      ret.resize(n);
      for (int i = 0; i < n; ++i) ret[i] = (ret[i] + ret[i]) % MOD;
      getlen((oth.size() << 1) + A.size());
      oth.resize(len);
      A.resize(len);
      oth = ntt(oth);
      A = ntt(A);
      for (int i = 0; i < len; ++i) oth[i] = qmul(qmul(oth[i], oth[i]), A[i]);
      oth = intt(oth);
      oth.resize(n);
      int iv = inver[len];
      for (int i = 0; i < n; ++i) {
        oth[i] = qmul(oth[i], iv);
      }
      for (int i = 0; i < n; ++i) ret[i] = qadd(ret[i], MOD - oth[i]);
    }
    return ret;
  }
} poly;
vector<int> operator*(vector<int> A, vector<int> B) { return poly.mul(A, B); }
vector<int> operator+(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], B[i]);
  return A;
}
vector<int> operator-(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], MOD - B[i]);
  return A;
}
vector<int> operator/(vector<int> A, vector<int> B) {
  return A * poly.inverse(B, A.size() - B.size() + 1);
}
vector<int> operator%(vector<int> A, vector<int> B) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  while (B.size() != 1 && B.back() == 0) B.pop_back();
  if (B.size() > A.size()) return A;
  vector<int> rem, mod;
  int n, m;
  n = A.size() - 1;
  m = B.size() - 1;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem = A / B;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem.resize(n - m + 1);
  reverse(rem.begin(), rem.end());
  mod = A - rem * B;
  mod.resize(m);
  return mod;
}
vector<int> der(vector<int> A) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  vector<int> ret(A.size() - 1);
  for (int i = 0; i < ret.size(); ++i) ret[i] = 1ll * (i + 1) * A[i + 1] % MOD;
  if (ret.empty()) return vector<int>(1, 0);
  return ret;
}
class MC {
  vector<vector<int> > RAM;
  vector<vector<int> > SIN;
  vector<int> Lc;
  vector<int> Rc;
  vector<int> ret;
  vector<int> x_;
  void fendge1(int l, int r, int& cnt) {
    if (l == r - 1) {
      Lc.push_back(0);
      Rc.push_back(0);
      RAM.push_back(SIN[l]);
      return;
    }
    RAM.push_back(vector<int>(0));
    Lc.push_back(0);
    Rc.push_back(0);
    int now = cnt;
    int mid = (l + r) >> 1;
    int L = ++cnt;
    fendge1(l, mid, cnt);
    int R = ++cnt;
    fendge1(mid, r, cnt);
    Lc[now] = L;
    Rc[now] = R;
    RAM[now] = RAM[L] * RAM[R];
  }
  void fendge2(int l, int r, int cnt, vector<int> p) {
    p = p % RAM[cnt];
    if (r - l <= 300) {
      for (int i = l; i <= r - 1; ++i) {
        int T = 1;
        for (int j = 0; j < p.size(); ++j) {
          ret[i] = qadd(ret[i], qmul(T, p[j]));
          T = qmul(T, x_[i]);
        }
      }
      return;
    }
    int mid = (l + r) >> 1;
    fendge2(l, mid, Lc[cnt], p);
    fendge2(mid, r, Rc[cnt], p);
  }

 public:
  vector<int> init(vector<int> p, vector<int> x) {
    x_ = x;
    Lc.clear();
    Rc.clear();
    RAM.clear();
    SIN.clear();
    ret.clear();
    ret.resize(x.size());
    for (int i = 0; i < x.size(); ++i) {
      SIN.push_back(vector<int>{(MOD - x[i]), 1});
    }
    int cnt = 0;
    fendge1(0, x.size(), cnt);
    fendge2(0, x.size(), 0, p);
    return ret;
  }
} mc;
vector<int> multiple_calculation(vector<int> p, vector<int> x) {
  return mc.init(p, x);
}
class ITP {
  vector<int> u;
  vector<int> v;
  vector<int> fm;
  vector<int> fendge(int l, int r) {
    if (l == r - 1) {
      return vector<int>{(MOD - u[l]), 1};
    }
    int mid = (l + r) >> 1;
    return fendge(l, mid) * fendge(mid, r);
  }
  pair<vector<int>, vector<int> > fendge2(int l, int r) {
    if (l == r - 1) {
      return {vector<int>{(MOD - u[l]), 1}, vector<int>{fm[l]}};
    }
    int mid = (l + r) >> 1;
    pair<vector<int>, vector<int> > L, R;
    L = fendge2(l, mid);
    R = fendge2(mid, r);
    return {L.first * R.first, L.first * R.second + R.first * L.second};
  }

 public:
  vector<int> solve(vector<pair<int, int> > x) {
    u.clear();
    v.clear();
    int n = x.size();
    for (auto it : x) u.push_back(it.first), v.push_back(it.second);
    vector<int> g = fendge(0, u.size());
    fm = multiple_calculation(der(g), u);
    for (int i = 0; i < n; ++i) {
      fm[i] = qmul(v[i], inv(fm[i]));
    }
    return fendge2(0, n).second;
  }
} itp;
vector<int> interpolation(vector<pair<int, int> > x) { return itp.solve(x); }
}  // namespace mypoly
using namespace mypoly;
const int MAXN = 5e4 + 1;
void add(int& A, int B) {
  A += B;
  if (A >= MOD) A -= MOD;
}
int n;
pair<int, vector<int> > solve(int n, int m) {
  if (m == 1) {
    vector<int> ret(n + 1, 1);
    ret[0] = 0;
    return make_pair(1, ret);
  }
  pair<int, vector<int> > small = solve(n, m / 2);
  int smallcyc = small.first;
  vector<int> smallline = small.second;
  smallline[1] = (m + 1) / 2;
  int anscyc = 0;
  if (n % 2 == 0) add(anscyc, 2ll * smallcyc % MOD);
  vector<int> odd(n + 1, 0);
  for (int i = 1; i <= n; ++i)
    if (i & 1) odd[i] = smallline[i];
  vector<int> orodd = odd;
  odd[0] = 1;
  for (int i = 1; i <= n; ++i) odd[i] = (MOD - odd[i]) % MOD;
  odd = poly.inverse(odd, n + 1);
  for (int i = 1; i <= n; ++i) orodd[i] = 1ll * i * orodd[i] % MOD;
  add(anscyc, (odd * orodd)[n]);
  vector<int> ansline(n + 1, 0);
  vector<int> even(n + 1, 0);
  for (int i = 1; i <= n; ++i)
    if (i % 2 == 0) even[i] = smallline[i];
  for (int i = 1; i <= n; ++i) add(ansline[i], odd[i]);
  vector<int> tmp = even * odd;
  for (int i = 1; i <= n; ++i) add(ansline[i], 2ll * tmp[i] % MOD);
  tmp = even * tmp;
  for (int i = 1; i <= n; ++i) add(ansline[i], tmp[i]);
  for (int i = 1; i <= n; ++i)
    if (i & 1) add(ansline[i], smallline[i]);
  return make_pair(anscyc, ansline);
}
int main() {
  int m;
  cin >> n >> m;
  cout << solve(n, m).first << endl;
  return 0;
}

```