#include<bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll=long long;
using P = pair<ll,ll>;
const long double PI=acos(-1);
const ll INF=1e18;
const int inf=1e9;
template <typename T>
bool chmin(T &a,const T& b){
  if (a>b){
    a=b;
    return true;
  }
  return false;
}
template<int MOD> struct Fp{
  ll val;
  constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  static constexpr int getmod() { return MOD; }
  constexpr Fp operator - () const noexcept {
    return val ? MOD - val : 0;
  }
  constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
  constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
  constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
  constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
  constexpr Fp& operator += (const Fp& r) noexcept {
    val += r.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  constexpr Fp& operator -= (const Fp& r) noexcept {
    val -= r.val;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr Fp& operator *= (const Fp& r) noexcept {
    val = val * r.val % MOD;
    return *this;
  }
  constexpr Fp& operator /= (const Fp& r) noexcept {
    ll a = r.val, b = MOD, u = 1, v = 0;
    while (b) {
      ll t = a / b;
      a -= t * b, swap(a, b);
      u -= t * v, swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr bool operator == (const Fp& r) const noexcept {
    return this->val == r.val;
  }
  constexpr bool operator != (const Fp& r) const noexcept {
    return this->val != r.val;
  }
  constexpr bool operator < (const Fp& r) const noexcept {
    return this->val < r.val;
  }
  friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
    is >> x.val;
    x.val %= MOD;
    if (x.val < 0) x.val += MOD;
    return is;
  }
  friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
    return os << x.val;
  }
  friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {
    Fp<MOD> res=1,r=a;
    while(n){
      if(n&1) res*=r;
      r*=r;
      n>>=1;
    }
    return res;
  }
  friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
  }
  ll get(){
      return val;
  }
  explicit operator bool()const{
		return val;
  }
};
template< uint32_t mod, bool fast = false >
struct MontgomeryModInt {
  using mint = MontgomeryModInt;
  using i32 = int32_t;
  using i64 = int64_t;
  using u32 = uint32_t;
  using u64 = uint64_t;
 
  static constexpr u32 get_r() {
    u32 ret = mod;
    for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;
    return ret;
  }
 
  static constexpr u32 r = get_r();
  static constexpr u32 n2 = -u64(mod) % mod;
 
  static_assert(r * mod == 1, "invalid, r * mod != 1");
  static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
  static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
 
  u32 a;
 
  MontgomeryModInt() : a{} {}
 
  MontgomeryModInt(const i64 &x)
      : a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}
 
  static constexpr u32 reduce(const u64 &b) {
    return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);
  }
 
  constexpr mint& operator+=(const mint &p) {
    if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }
 
  constexpr mint& operator-=(const mint &p) {
    if(i32(a -= p.a) < 0) a += 2 * mod;
    return *this;
  }
 
  constexpr mint& operator*=(const mint &p) {
    a = reduce(u64(a) * p.a);
    return *this;
  }
 
  constexpr mint& operator/=(const mint &p) {
    *this *= modinv(p);
    return *this;
  }
 
  constexpr mint operator-() const { return mint() - *this; }
 
  constexpr mint operator+(const mint &p) const { return mint(*this) += p; }
 
  constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }
 
  constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }
 
  constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }
 
  constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }
 
  constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }
 
  u32 get() const {
    u32 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }
 
  friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {
    MontgomeryModInt<mod> ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
 
  friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {
        u64 a = r.get(), b = mod, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return MontgomeryModInt<mod>(u);
  }
 
  friend ostream &operator<<(ostream &os, const mint &p) {
    return os << p.get();
  }
 
  friend istream &operator>>(istream &is, mint &a) {
    i64 t;
    is >> t;
    a = mint(t);
    return is;
  }
  static constexpr u32 getmod() { return mod; }
};
template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{
  int n;
  vector<T> dat;
  SegmentTree(int N){
    n=1;
    while(n<N)n*=2;
    dat.assign(2*n,e());
  }
  void add(int k,T x){
    k+=n;
    dat[k]+=x;
    while(k){
      k>>=1;
      dat[k]=op(dat[k*2],dat[k*2+1]);
    }
  }
  void apply(int k,T x){
    k+=n;
    dat[k]=op(dat[k],x);
    while(k){
      k>>=1;
      dat[k]=op(dat[k*2],dat[k*2+1]);
    }
  }
  void set(int k,T x){
    k+=n;
    dat[k]=x;
    while(k){
      k>>=1;
      dat[k]=op(dat[k*2],dat[k*2+1]);
    }
  }
  T query(int l,int r){
    T prodl=e(),prodr=e();
    l+=n;
    r+=n;
    while(l<r){
      if(l&1) prodl=op(prodl,dat[l++]);
      if(r&1) prodr=op(dat[--r],prodr);
      l>>=1;
      r>>=1;
    }
    return op(prodl,prodr);
  }
};
template<class S,S (*op)(S,S),S (*e)(),class F,S (*mapping)(F,S),F (*composition)(F,F),F (*id)()>
struct LazySegTree{
  private:
  int _n,size=1,idx=0;
  vector<S>seq;
  vector<F>lazy;
  void update(int k){seq[k]=op(seq[2*k],seq[2*k+1]);}
  void all_apply(int k,F f){
    seq[k]=mapping(f,seq[k]);
    if(k<size)lazy[k]=composition(f,lazy[k]);
  }
  void eval(int k){
    all_apply(2*k,lazy[k]);
    all_apply(2*k+1,lazy[k]);
    lazy[k]=id();
  }
  public:
  explicit LazySegTree(int n):LazySegTree(vector<S>(n,e())){}
  explicit LazySegTree(const vector<S>&v):_n(int(v.size())){
    while(size<_n)size<<=1,idx++;
    seq=vector<S>(2*size,e());
    lazy=vector<F>(2*size,id());
    for(int i=0;i<_n;i++)seq[size+i]=v[i];
    for(int i=size-1;i>=1;i--)update(i);
  }
  void set(int p,S x){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    seq[p]=x;
    for(int i=1;i<=idx;i++)update(p>>i);
  }
  S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = idx; i >= 1; i--) eval(p >> i);
        return seq[p];
  }
  S operator[](int p){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    return seq[p];
  }
  S query(int l,int r){
    if(l==r)return e();
    S sml=e(),smr=e();
    l+=size,r+=size;
    for(int i=idx;i>=1;i--){
      if(((l>>i)<<i)!=l)eval(l>>i);
      if(((r>>i)<<i)!=r)eval(r>>i);
    }
    while(l<r){
      if(l&1)sml=op(sml,seq[l++]);
      if(r&1)smr=op(seq[--r],smr);
      l>>=1,r>>=1;
    }
    return op(sml,smr);
  }
  S all_query()const{return seq[1];}
  void apply(int p,F f){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    seq[p]=mapping(f,seq[p]);
    for(int i=1;i<=idx;i++)update(p>>i);
  }
  void apply(int l,int r,F f){
    if(l==r)return ;
    l+=size;
    r+=size;
    for(int i=idx;i>=1;i--){
      if(((l>>i)<<i)!=l)eval(l>>i);
      if(((r>>i)<<i)!=r)eval((r-1)>>i);
    }
    int l2=l,r2=r;
    while(l<r){
      if(l&1)all_apply(l++,f);
      if(r&1)all_apply(--r,f);
      l>>=1;
      r>>=1;
    }
    l=l2,r=r2;
    for(int i=1;i<=idx;i++){
      if(((l>>i)<<i)!=l)update(l>>i);
      if(((r>>i)<<i)!=r)update((r-1)>>i);
    }
  }
};
ll mod(ll a,ll MOD){
    if(a<0) a+=MOD;
    return a%MOD;
}
ll modpow(ll a,ll n,ll mod){
  ll res=1;
  a%=mod;
  while (n>0){
    if (n & 1) res*=a;
    a *= a;
    a%=mod;
    n >>= 1;
    res%=mod;
  }
  return res;
}
vector<P> prime_factorize(ll N) {
  vector<P> res;
  for (ll a = 2; a * a <= N; ++a) {
    if (N % a != 0) continue;
    ll ex = 0;
    while(N % a == 0){
      ++ex;
      N /= a;
    }
    res.push_back({a, ex});
  }
  if (N != 1) res.push_back({N, 1});
  return res;
}
ll modinv(ll a, ll mod) {
    ll b = mod, u = 1, v = 0;
    while (b) {
        ll t = a/b;
        a -= t * b, swap(a, b);
        u -= t * v, swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
ll extGcd(ll a, ll b, ll &p, ll &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    ll d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}
P ChineseRem(const vector<ll> &b, const vector<ll> &m) {
  ll r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    ll p, q;
    ll d = extGcd(M, m[i], p, q);
    if ((b[i] - r) % d != 0) return make_pair(0, -1);
    ll tmp = (b[i] - r) / d * p % (m[i]/d);
    r += M * tmp;
    M *= m[i]/d;
  }
  return make_pair(mod(r, M), M);
}
template< typename T >
struct Combination {
  vector< T > _fact, _rfact, _inv;

  Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
    _fact[0] = _rfact[sz] = _inv[0] = 1;
    for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
    _rfact[sz] /= _fact[sz];
    for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
    for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
  }

  inline T fact(int k) const { return _fact[k]; }

  inline T rfact(int k) const { return _rfact[k]; }

  inline T inv(int k) const { return _inv[k]; }

  T P(int n, int r) const {
    if(r < 0 || n < r) return 0;
    return fact(n) * rfact(n - r);
  }

  T C(int p, int q) const {
    if(q < 0 || p < q) return 0;
    return fact(p) * rfact(q) * rfact(p - q);
  }

  T H(int n, int r) const {
    if(n < 0 || r < 0) return (0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
//fast Input by yosupo
#include <unistd.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <cstring>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
namespace fastio{
/*
  quote from yosupo's submission in Library Checker
*/
int bsr(unsigned int n) {
    return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long n) {
    return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long long n) {
    return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned __int128 n) {
    unsigned long long low = (unsigned long long)(n);
    unsigned long long high = (unsigned long long)(n >> 64);
    return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low);
}
 
namespace internal {
 
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;
 
template <class T>
using is_integral =
    typename std::conditional<std::is_integral<T>::value ||
                                  internal::is_signed_int128<T>::value ||
                                  internal::is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;
 
template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;
 
template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;
 
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
 
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
 
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
 
}  // namespace internal
struct Scanner {
  public:
    Scanner(const Scanner&) = delete;
    Scanner& operator=(const Scanner&) = delete;
 
    Scanner(FILE* fp) : fd(fileno(fp)) {}
 
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
 
    int read_unsafe() { return 0; }
    template <class H, class... T> int read_unsafe(H& h, T&... t) {
        bool f = read_single(h);
        if (!f) return 0;
        return 1 + read_unsafe(t...);
    }
 
    int close() { return ::close(fd); }
 
  private:
    static constexpr int SIZE = 1 << 15;
 
    int fd = -1;
    std::array<char, SIZE + 1> line;
    int st = 0, ed = 0;
    bool eof = false;
 
    bool read_single(std::string& ref) {
        if (!skip_space()) return false;
        ref = "";
        while (true) {
            char c = top();
            if (c <= ' ') break;
            ref += c;
            st++;
        }
        return true;
    }
    bool read_single(double& ref) {
        std::string s;
        if (!read_single(s)) return false;
        ref = std::stod(s);
        return true;
    }
 
    template <class T,
              std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
    bool read_single(T& ref) {
        if (!skip_space<50>()) return false;
        ref = top();
        st++;
        return true;
    }
 
    template <class T,
              internal::is_signed_int_t<T>* = nullptr,
              std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
    bool read_single(T& sref) {
        using U = internal::to_unsigned_t<T>;
        if (!skip_space<50>()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        U ref = 0;
        do {
            ref = 10 * ref + (line[st++] & 0x0f);
        } while (line[st] >= '0');
        sref = neg ? -ref : ref;
        return true;
    }
    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
    bool read_single(U& ref) {
        if (!skip_space<50>()) return false;
        ref = 0;
        do {
            ref = 10 * ref + (line[st++] & 0x0f);
        } while (line[st] >= '0');
        return true;
    }
 
    bool reread() {
        if (ed - st >= 50) return true;
        if (st > SIZE / 2) {
            std::memmove(line.data(), line.data() + st, ed - st);
            ed -= st;
            st = 0;
        }
        if (eof) return false;
        auto u = ::read(fd, line.data() + ed, SIZE - ed);
        if (u == 0) {
            eof = true;
            line[ed] = '\0';
            u = 1;
        }
        ed += int(u);
        line[ed] = char(127);
        return true;
    }
 
    char top() {
        if (st == ed) {
            bool f = reread();
            assert(f);
        }
        return line[st];
    }
 
    template <int TOKEN_LEN = 0>
    bool skip_space() {
        while (true) {
            while (line[st] <= ' ') st++;   
            if (ed - st > TOKEN_LEN) return true;
            if (st > ed) st = ed;
            for (auto i = st; i < ed; i++) {
                if (line[i] <= ' ') return true;
            }
            if (!reread()) return false;
        }
    }
};

//fast Output by ei1333
/**
 * @brief Printer(高速出力)
 */
struct Printer {
public:
  explicit Printer(FILE *fp) : fp(fp) {}

  ~Printer() { flush(); }

  template< bool f = false, typename T, typename... E >
  void write(const T &t, const E &... e) {
    if(f) write_single(' ');
    write_single(t);
    write< true >(e...);
  }

  template< typename... T >
  void writeln(const T &...t) {
    write(t...);
    write_single('\n');
  }

  void flush() {
    fwrite(line, 1, st - line, fp);
    st = line;
  }

private:
  FILE *fp = nullptr;
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  char small[32] = {};
  char *st = line;

  template< bool f = false >
  void write() {}

  void write_single(const char &t) {
    if(st + 1 >= line + line_size) flush();
    *st++ = t;
  }

  template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >
  void write_single(T s) {
    if(st + int_digits >= line + line_size) flush();
    if(s == 0) {
      write_single('0');
      return;
    }
    if(s < 0) {
      write_single('-');
      s = -s;
    }
    char *mp = small + sizeof(small);
    typename make_unsigned< T >::type y = s;
    size_t len = 0;
    while(y > 0) {
      *--mp = y % 10 + '0';
      y /= 10;
      ++len;
    }
    memmove(st, mp, len);
    st += len;
  }

  void write_single(const string &s) {
    for(auto &c : s) write_single(c);
  }

  void write_single(const char *s) {
    while(*s != 0) write_single(*s++);
  }

  template< typename T >
  void write_single(const vector< T > &s) {
    for(size_t i = 0; i < s.size(); i++) {
      if(i) write_single(' ');
      write_single(s[i]);
    }
  }
};

}; //namespace fastio
using u64=unsigned long long;
u64 RNG_64() {
  static uint64_t x_
      = uint64_t(chrono::duration_cast<chrono::nanoseconds>(
                     chrono::high_resolution_clock::now().time_since_epoch())
                     .count())
        * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
struct modint61 {
  static constexpr bool is_modint = true;
  static constexpr ll mod = (1LL << 61) - 1;
  ll val;
  constexpr modint61(const ll x = 0) : val(x) {
    while (val < 0) val += mod;
    while (val >= mod) val -= mod;
  }
  bool operator<(const modint61 &other) const {
    return val < other.val;
  } // To use std::map

  bool operator==(const modint61 &p) const { return val == p.val; }
  bool operator!=(const modint61 &p) const { return val != p.val; }
  modint61 &operator+=(const modint61 &p) {
    if ((val += p.val) >= mod) val -= mod;
    return *this;
  }
  modint61 &operator-=(const modint61 &p) {
    if ((val += mod - p.val) >= mod) val -= mod;
    return *this;
  }
  modint61 &operator*=(const modint61 &p) {
    ll a = val, b = p.val;
    const ll MASK30 = (1LL << 30) - 1;
    const ll MASK31 = (1LL << 31) - 1;
    const ll MASK61 = (1LL << 61) - 1;
    ll au = a >> 31, ad = a & MASK31;
    ll bu = b >> 31, bd = b & MASK31;
    ll x = ad * bu + au * bd;
    ll xu = x >> 30, xd = x & MASK30;
    x = au * bu * 2 + xu + (xd << 31) + ad * bd;
    xu = x >> 61, xd = x & MASK61;
    x = xu + xd;
    if (x >= MASK61) x -= MASK61;
    val = x;
    return *this;
  }
  modint61 operator-() const { return modint61(get_mod() - val); }
  modint61 &operator/=(const modint61 &p) {
    *this *= p.inverse();
    return *this;
  }
  modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
  modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
  modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
  modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }

  modint61 inverse() const {
    ll a = val, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b), swap(u -= t * v, v);
    }
    return modint61(u);
  }
  modint61 pow(int64_t n) const {
    modint61 ret(1), mul(val);
    while (n > 0) {
      if (n & 1) ret = ret * mul;
      mul = mul * mul;
      n >>= 1;
    }
    return ret;
  }
  static constexpr ll get_mod() { return mod; }
#ifdef FASTIO
  void write() { fastio::printer.write(val); }
  void read() { fastio::scanner.read(val); }
#endif
};
struct RollingHash {
  using mint = modint61;
  static constexpr u64 mod = mint::get_mod();
  const mint base;
  vector<mint> power;

  static inline mint generate_base() { return RNG(mod); }

  inline void expand(size_t sz) {
    if (power.size() < sz + 1) {
      int pre_sz = (int)power.size();
      power.resize(sz + 1);
      for(int i=pre_sz - 1;i<sz;i++) power[i + 1] = power[i] * base;
    }
  }

  explicit RollingHash(mint base = generate_base()) : base(base), power{1} {}

  template <typename STRING>
  vector<mint> build(const STRING& s) const {
    int sz = s.size();
    vector<mint> hashed(sz + 1);
    for (int i = 0; i < sz; i++) { hashed[i + 1] = hashed[i] * base + s[i]; }
    return hashed;
  }

  mint query(const vector<mint>& s, int l, int r) {
    expand(r - l);
    return (s[r] - s[l] * power[r - l]).val;
  }

  mint combine(mint h1, mint h2, int h2len) {
    expand(h2len);
    return h1 * power[h2len] + h2;
  }

  mint add_char(mint h, int x) { return h * base + mint(x); }

  int lcp(const vector<mint>& a, int l1, int r1, const vector<mint>& b, int l2,
          int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = 0, high = len + 1;
    while (high - low > 1) {
      int mid = (low + high) / 2;
      if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))
        low = mid;
      else
        high = mid;
    }
    return low;
  }
};
inline constexpr int msb(u64 x) {
    int res = x ? 0 : -1;
    if (x & 0xFFFFFFFF00000000) x &= 0xFFFFFFFF00000000, res += 32;
    if (x & 0xFFFF0000FFFF0000) x &= 0xFFFF0000FFFF0000, res += 16;
    if (x & 0xFF00FF00FF00FF00) x &= 0xFF00FF00FF00FF00, res += 8;
    if (x & 0xF0F0F0F0F0F0F0F0) x &= 0xF0F0F0F0F0F0F0F0, res += 4;
    if (x & 0xCCCCCCCCCCCCCCCC) x &= 0xCCCCCCCCCCCCCCCC, res += 2;
    return res + ((x & 0xAAAAAAAAAAAAAAAA) ? 1 : 0);
}

inline constexpr int ceil_log2(u64 x) { return x ? msb(x - 1) + 1 : 0; }
template<class T> class infinity {
public:
    static constexpr T value = std::numeric_limits<T>::max() / 2;
    static constexpr T mvalue = std::numeric_limits<T>::min() / 2;
    static constexpr T max = std::numeric_limits<T>::max();
    static constexpr T min = std::numeric_limits<T>::min();
};

#if __cplusplus <= 201402L
template<class T> constexpr T infinity<T>::value;
template<class T> constexpr T infinity<T>::mvalue;
template<class T> constexpr T infinity<T>::max;
template<class T> constexpr T infinity<T>::min;
#endif
template<class T = ll, bool is_max = false> class LiChaoTree {
private:
    struct Line {
        T a, b;
        int idx;
        T get(T x) const { return a * x + b; }
        Line() = default;
        Line(T a, T b, int id) : a(a), b(b), idx(id) {}
    };
    int line_count = 0;
    int ori, n;
    std::vector<T> xs;
    std::vector<Line> lns;
    void add_line(int k, int a, int b, const Line& line) {
        if (a + 1 == b) {
            if (line.get(xs[a]) < lns[k].get(xs[a])) lns[k] = line;
            return;
        }
        int m = (a + b) >> 1;
        T x1 = lns[k].get(xs[a]), x2 = line.get(xs[a]);
        T y1 = lns[k].get(xs[b - 1]), y2 = line.get(xs[b - 1]);
        if (x1 <= x2 && y1 <= y2) return;
        if (x2 <= x1 && y2 <= y1) {
            lns[k] = line;
            return;
        }
        if (lns[k].get(xs[m]) <= line.get(xs[m])) {
            if (y1 < y2) add_line(k << 1, a, m, line);
            else add_line(k << 1 | 1, m, b, line);
        }
        else {
            if (y1 < y2) add_line(k << 1 | 1, m, b, lns[k]);
            else add_line(k << 1, a, m, lns[k]);
            lns[k] = line;
        }
    }
    void add_segment(int k, int a, int b, int l, int r, const Line& line) {
        if (l <= a && b <= r) {
            add_line(k, a, b, line);
            return;
        }
        if (r <= a || b <= l) return;
        int m = (a + b) >> 1;
        add_segment(k << 1, a, m, l, r, line);
        add_segment(k << 1 | 1, m, b, l, r, line);
    }

public:
    LiChaoTree() : LiChaoTree({0}) {}
    LiChaoTree(const std::vector<T>& xs_) { init(xs_); }
    void init(const std::vector<T>& xs_) {
        xs = xs_.empty() ? std::vector<T>{0} : xs_;
        ori = xs.size();
        n = 1 << ceil_log2(ori);
        xs.reserve(n);
        for(int i=xs_.size();i<n;i++) xs.push_back(xs_[i] + 1);
        lns.assign(n << 1,
                   Line{0, is_max ? infinity<T>::min : infinity<T>::max, -1});
    }
    int add_segment(int l, int r, T x, T y) {
        assert(0 <= l && l <= r && r <= ori);
        add_segment(1, 0, n, l, r,
                    Line{is_max ? -x : x, is_max ? -y : y, line_count});
        return line_count++;
    }
    int add_line(T x, T y) {
        add_line(1, 0, n, Line{is_max ? -x : x, is_max ? -y : y, line_count});
        return line_count++;
    }
    T get_min(int k) const {
        int x = k + n;
        T res = lns[x].get(xs[k]);
        while (x >>= 1) {
            const T y = lns[x].get(xs[k]);
            if(is_max) chmin(res, -y );
            else chmin(res, y);
        }
        return res;
    }
    struct line {
        T a, b;
        int idx;
    };
    line get_min_line(int k) const {
        int x = k + n;
        T mn = lns[x].get(xs[k]);
        Line res = lns[x];
        while (x >>= 1) {
            const T y = lns[x].get(xs[k]);
            if (chmin(mn, is_max ? -y : y)) res = lns[x];
        }
        return line{is_max ? -res.a : res.a, is_max ? -res.b : res.b, res.idx};
    }
};
using mint=MontgomeryModInt<998244353>;
int main(){
    fastio::Scanner sc(stdin);
    fastio::Printer pr(stdout);
    #define in(...) sc.read(__VA_ARGS__)
    #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
    #define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
    #define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
    #define out(...) pr.write(__VA_ARGS__)
    #define outln(...) pr.writeln(__VA_ARGS__)
    #define outspace(...) pr.write(__VA_ARGS__),pr.write(' ')
    #define rall(v) (v).rbegin(), (v).rend()
    #define fi first
    #define se second
    /*
        
    */
    INT(n,k);
    assert(1<=n&&n<=100000&&1<=k&&k<=n*2+4);
    Combination<mint> C(200200);
    if(n==1){
        mint ans=0;
        for(int i=0;i<6;i++){
            if(k%(6/gcd(6,i))==0) ans+=C.C(i,k/(6/gcd(6,i)));
        }
        outln(ans.get());
        return 0;
    }
    mint ans=C.C(n*2+4,k);
    if(n%2==1&&k%2==1) ans+=C.C(n+1,(k-1)/2)*2;
    else if(n%2==1&&k%2==0) ans+=C.C(n+1,k/2)+C.C(n+1,(k-2)/2);
    else if(n%2==0&&k%2==0) ans+=C.C(n+2,k/2);
    if(k%2==0) ans+=C.C(n+2,k/2)*2;
    ans*=C.inv(4);
    outln(ans.get());
}