#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, inv2 = 499122177, inv6 = 166374059;
int n, m, f1[150001], f2[150001], f3[150001], s1[150001], s2[150001],
    s3[150001], ans[150001], invf[150001], invv[21], g[21][150001],
    id[21][150001], ff[150001], ss;
inline int add(int a, int b) {
  int c = a + b;
  if (c >= mod) c = c - mod;
  return c;
}
inline int del(int a, int b) {
  int c = a - b;
  if (c < 0) c = c + mod;
  return c;
}
inline int mul(int a, int b) { return 1ll * a * b % mod; }
inline int ksm(int a, int b) {
  int s = 1;
  while (b) {
    if (b & 1) s = mul(s, a);
    a = mul(a, a);
    b = b >> 1;
  }
  return s;
}
inline int getlen(int a) {
  int s = 0;
  while ((1 << s) < a) s++;
  return s;
}
inline void ntt(int a[], int cnt, bool fl) {
  int len = (1 << cnt);
  for (int i = 0; i < len; i++)
    if (i < id[cnt][i]) swap(a[i], a[id[cnt][i]]);
  for (int k = 1; k <= cnt; k++) {
    int len2 = (1 << k);
    int mid = (1 << (k - 1));
    for (int i = 0; i < len; i = i + len2) {
      for (int j = 0; j < mid; j++) {
        int x = a[i + j];
        int y = mul(a[i + mid + j], g[k][j]);
        a[i + j] = add(x, y);
        a[i + mid + j] = del(x, y);
      }
    }
  }
  if (fl) return;
  for (int i = 0; i < len; i++) a[i] = mul(a[i], invv[cnt]);
  reverse(a + 1, a + len);
}
void inv(int a[], int b[], int len) {
  b[0] = ksm(a[0], mod - 2);
  int cnt = getlen(len) + 1, sum = 2;
  for (int i = 1; i < cnt; i++) {
    for (int j = 0; j < sum; j++) ff[j] = a[j];
    sum = sum << 1;
    ntt(ff, i + 1, 1);
    ntt(b, i + 1, 1);
    for (int j = 0; j < sum; j++) {
      b[j] = del(add(b[j], b[j]), mul(ff[j], mul(b[j], b[j])));
      ff[j] = 0;
    }
    ntt(b, i + 1, 0);
    for (int j = sum >> 1; j < sum; j++) b[j] = 0;
  }
  for (int i = len; i < sum; i++) b[i] = 0;
}
void init() {
  int cnt = getlen(n + n + 2);
  invv[0] = 1;
  g[0][0] = 1;
  for (int i = 1; i <= cnt; i++) {
    int sum = (1 << i), s = (1 << (i - 1));
    g[i][0] = 1;
    g[i][1] = ksm(3, (mod - 1) / sum);
    id[i][1] = s;
    invv[i] = ksm(sum, mod - 2);
    for (int j = 2; j < sum; j++) {
      g[i][j] = mul(g[i][1], g[i][j - 1]);
      if (j & 1)
        id[i][j] = (id[i][j >> 1] >> 1) + s;
      else
        id[i][j] = (id[i][j >> 1] >> 1);
    }
  }
}
int getans1(int a) { return mul(mul(a, add(a, 1)), inv2); }
int getans2(int a) {
  return mul(mul(mul(a, add(a, 1)), add(mul(a, 2), 1)), inv6);
}
void ins(int a) {
  int cnt = getlen(n + n + 2);
  int len = (1 << cnt);
  for (int i = 0; i < len; i++) {
    s1[i] = f1[i];
    s2[i] = f2[i];
    s3[i] = 0;
  }
  for (int i = 0; i <= n; i++) {
    s3[i] = mul(s1[i], i);
    s1[i] = del(0, s1[i]);
  }
  s1[0] = add(s1[0], 1);
  inv(s1, invf, n + 1);
  ntt(invf, cnt, 1);
  ntt(s3, cnt, 1);
  for (int i = 0; i < len; i++) {
    ans[i] = mul(s3[i], invf[i]);
    s3[i] = 0;
    invf[i] = 0;
    s1[i] = 0;
  }
  ntt(ans, cnt, 0);
  for (int i = n + 1; i < len; i++) ans[i] = 0;
  ss = add(ss, mul(ans[n], a));
}
void solve(int a, int c) {
  if (a == 1) {
    f1[1] = 1;
    f2[0] = 1;
    if (!(n & 1)) ss = add(ss, c);
    return;
  }
  solve(a / 2, add(c, c));
  int cnt = getlen(n + n + 2);
  int len = (1 << cnt);
  ntt(f2, cnt, 1);
  for (int i = 0; i < len; i++) f2[i] = mul(f2[i], f2[i]);
  ntt(f2, cnt, 0);
  for (int i = n + 1; i < len; i++) f2[i] = 0;
  for (int i = 0; i <= n; i++) f3[i] = del(0, f1[i]);
  f3[0] = add(f3[0], 1);
  inv(f3, invf, n + 1);
  ntt(f1, cnt, 1);
  ntt(invf, cnt, 1);
  ntt(f2, cnt, 1);
  for (int i = 0; i < len; i++) {
    ans[i] = add(mul(f2[i], invf[i]), f1[i]);
    f2[i] = 0;
    invf[i] = 0;
    f1[i] = 0;
    f3[i] = 0;
  }
  ntt(ans, cnt, 0);
  for (int i = n + 1; i < len; i++) ans[i] = 0;
  ans[0] = 1;
  ans[1] = (a + 1) / 2;
  ans[2] = getans1(a - (a + 1) / 2);
  ans[3] = getans2(a - (a + 1) / 2);
  for (int i = 0; i <= n; i++) {
    if (i & 1)
      f1[i] = ans[i];
    else
      f2[i] = ans[i];
  }
  if (!(n & 1)) ins(c);
}
int main() {
  scanf("%d%d", &n, &m);
  init();
  solve(m, 1);
  if (n & 1) ins(1);
  printf("%d\n", ss);
}

### Prompt

In CPP, your task is to solve 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, inv2 = 499122177, inv6 = 166374059;
int n, m, f1[150001], f2[150001], f3[150001], s1[150001], s2[150001],
    s3[150001], ans[150001], invf[150001], invv[21], g[21][150001],
    id[21][150001], ff[150001], ss;
inline int add(int a, int b) {
  int c = a + b;
  if (c >= mod) c = c - mod;
  return c;
}
inline int del(int a, int b) {
  int c = a - b;
  if (c < 0) c = c + mod;
  return c;
}
inline int mul(int a, int b) { return 1ll * a * b % mod; }
inline int ksm(int a, int b) {
  int s = 1;
  while (b) {
    if (b & 1) s = mul(s, a);
    a = mul(a, a);
    b = b >> 1;
  }
  return s;
}
inline int getlen(int a) {
  int s = 0;
  while ((1 << s) < a) s++;
  return s;
}
inline void ntt(int a[], int cnt, bool fl) {
  int len = (1 << cnt);
  for (int i = 0; i < len; i++)
    if (i < id[cnt][i]) swap(a[i], a[id[cnt][i]]);
  for (int k = 1; k <= cnt; k++) {
    int len2 = (1 << k);
    int mid = (1 << (k - 1));
    for (int i = 0; i < len; i = i + len2) {
      for (int j = 0; j < mid; j++) {
        int x = a[i + j];
        int y = mul(a[i + mid + j], g[k][j]);
        a[i + j] = add(x, y);
        a[i + mid + j] = del(x, y);
      }
    }
  }
  if (fl) return;
  for (int i = 0; i < len; i++) a[i] = mul(a[i], invv[cnt]);
  reverse(a + 1, a + len);
}
void inv(int a[], int b[], int len) {
  b[0] = ksm(a[0], mod - 2);
  int cnt = getlen(len) + 1, sum = 2;
  for (int i = 1; i < cnt; i++) {
    for (int j = 0; j < sum; j++) ff[j] = a[j];
    sum = sum << 1;
    ntt(ff, i + 1, 1);
    ntt(b, i + 1, 1);
    for (int j = 0; j < sum; j++) {
      b[j] = del(add(b[j], b[j]), mul(ff[j], mul(b[j], b[j])));
      ff[j] = 0;
    }
    ntt(b, i + 1, 0);
    for (int j = sum >> 1; j < sum; j++) b[j] = 0;
  }
  for (int i = len; i < sum; i++) b[i] = 0;
}
void init() {
  int cnt = getlen(n + n + 2);
  invv[0] = 1;
  g[0][0] = 1;
  for (int i = 1; i <= cnt; i++) {
    int sum = (1 << i), s = (1 << (i - 1));
    g[i][0] = 1;
    g[i][1] = ksm(3, (mod - 1) / sum);
    id[i][1] = s;
    invv[i] = ksm(sum, mod - 2);
    for (int j = 2; j < sum; j++) {
      g[i][j] = mul(g[i][1], g[i][j - 1]);
      if (j & 1)
        id[i][j] = (id[i][j >> 1] >> 1) + s;
      else
        id[i][j] = (id[i][j >> 1] >> 1);
    }
  }
}
int getans1(int a) { return mul(mul(a, add(a, 1)), inv2); }
int getans2(int a) {
  return mul(mul(mul(a, add(a, 1)), add(mul(a, 2), 1)), inv6);
}
void ins(int a) {
  int cnt = getlen(n + n + 2);
  int len = (1 << cnt);
  for (int i = 0; i < len; i++) {
    s1[i] = f1[i];
    s2[i] = f2[i];
    s3[i] = 0;
  }
  for (int i = 0; i <= n; i++) {
    s3[i] = mul(s1[i], i);
    s1[i] = del(0, s1[i]);
  }
  s1[0] = add(s1[0], 1);
  inv(s1, invf, n + 1);
  ntt(invf, cnt, 1);
  ntt(s3, cnt, 1);
  for (int i = 0; i < len; i++) {
    ans[i] = mul(s3[i], invf[i]);
    s3[i] = 0;
    invf[i] = 0;
    s1[i] = 0;
  }
  ntt(ans, cnt, 0);
  for (int i = n + 1; i < len; i++) ans[i] = 0;
  ss = add(ss, mul(ans[n], a));
}
void solve(int a, int c) {
  if (a == 1) {
    f1[1] = 1;
    f2[0] = 1;
    if (!(n & 1)) ss = add(ss, c);
    return;
  }
  solve(a / 2, add(c, c));
  int cnt = getlen(n + n + 2);
  int len = (1 << cnt);
  ntt(f2, cnt, 1);
  for (int i = 0; i < len; i++) f2[i] = mul(f2[i], f2[i]);
  ntt(f2, cnt, 0);
  for (int i = n + 1; i < len; i++) f2[i] = 0;
  for (int i = 0; i <= n; i++) f3[i] = del(0, f1[i]);
  f3[0] = add(f3[0], 1);
  inv(f3, invf, n + 1);
  ntt(f1, cnt, 1);
  ntt(invf, cnt, 1);
  ntt(f2, cnt, 1);
  for (int i = 0; i < len; i++) {
    ans[i] = add(mul(f2[i], invf[i]), f1[i]);
    f2[i] = 0;
    invf[i] = 0;
    f1[i] = 0;
    f3[i] = 0;
  }
  ntt(ans, cnt, 0);
  for (int i = n + 1; i < len; i++) ans[i] = 0;
  ans[0] = 1;
  ans[1] = (a + 1) / 2;
  ans[2] = getans1(a - (a + 1) / 2);
  ans[3] = getans2(a - (a + 1) / 2);
  for (int i = 0; i <= n; i++) {
    if (i & 1)
      f1[i] = ans[i];
    else
      f2[i] = ans[i];
  }
  if (!(n & 1)) ins(c);
}
int main() {
  scanf("%d%d", &n, &m);
  init();
  solve(m, 1);
  if (n & 1) ins(1);
  printf("%d\n", ss);
}

```