#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
vector<int> fact;
vector<int> ifact;
vector<int> pow2;
const int MOD = 998244353;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
void radd(int &a, int b)
{
	a=add(a,b); 
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
	a=mult(a,b);
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
}

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const ld PI = acos((ld)-1);
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
mt19937 rng; // or mt19937_64

void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << h; if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
	#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
	#define dbg(...) 42
#endif

const int root = 3;
struct mi {
	typedef decay<decltype(MOD)>::type T; 
 	/// don't silently convert to T
	T v; explicit operator T() const { return v; }
	mi() { v = 0; }
	mi(ll _v) { 
		v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mi& a, const mi& b) { 
		return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { 
		return !(a == b); }
	friend bool operator<(const mi& a, const mi& b) { 
		return a.v < b.v; }
   
	mi& operator+=(const mi& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	mi& operator-=(const mi& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	mi& operator*=(const mi& m) { 
		v = (ll)v*m.v%MOD; return *this; }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi pow(mi a, ll p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend mi inv(const mi& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mi operator-() const { return mi(-v); }
	mi& operator++() { return *this += 1; }
	mi& operator--() { return *this -= 1; }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const mi &m)
	{
		os<<int(m);
		return os;
	}
};

typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;

vector<vmi> comb;
void genComb(int SZ) {
	comb.assign(SZ,vmi(SZ)); comb[0][0] = 1;
	FOR(i,1,SZ) F0R(j,i+1) 
		comb[i][j] = comb[i-1][j]+(j?comb[i-1][j-1]:0);
}

// For p < 2^30 there is also e.g. (5<<25, 3), (7<<26, 3) 
/// (479<<21, 3) and (483<<21, 5). Last two are > 10^9.
void genRoots(vmi& roots) { // REPLACE DEF OF MOD
	int n = sz(roots); mi r = pow(mi(root),(MOD-1)/n);
	roots[0] = 1; FOR(i,1,n) roots[i] = roots[i-1]*r; 
}
int size(int s) { return s > 1 ? 32-__builtin_clz(s-1) : 0; }
template<class T> void fft(vector<T>& a, 
  const vector<T>& rts, bool inv = 0) {
	int n = sz(a);
	for (int i = 1, j = 0; i < n; i++) { 
		int bit = n>>1; for (; j&bit; bit /= 2) j ^= bit;
		j ^= bit; if (i < j) swap(a[i],a[j]);
	} // sort #s from 0 to n-1 by reverse binary
	for (int len = 1; len < n; len *= 2)
		for (int i = 0; i < n; i += 2*len) F0R(j,len) {
			T u = a[i+j], v = a[i+j+len]*rts[n/2/len*j];
			a[i+j] = u+v, a[i+j+len] = u-v;
		}
	if (inv) {
		reverse(1+all(a));
		T i = T(1)/T(n); trav(x,a) x *= i; 
	}
}
template<class T> vector<T> mul(vector<T> a, vector<T> b) {
	if (!min(sz(a),sz(b))) return {};
	int s = sz(a)+sz(b)-1, n = 1<<size(s);
	vector<T> roots(n); genRoots(roots);
	a.rsz(n), fft(a,roots); b.rsz(n), fft(b,roots);
	F0R(i,n) a[i] *= b[i];
	fft(a,roots,1); a.rsz(s); return a;
}
typedef mi T; using poly = vector<T>;
void remz(poly& p) { while (sz(p) && p.bk==0) p.pop_back(); }
poly rev(poly p) { reverse(all(p)); return p; }
poly shift(poly p, int x) { p.insert(begin(p),x,0); return p; }
poly RSZ(poly p, int x) { p.rsz(x); return p; }
T eval(const poly& p, T x) {
	T res = 0; R0F(i,sz(p)) res = x*res+p[i]; 
	return res; }
poly dif(const poly& p) { // differentiate
	poly res; FOR(i,1,sz(p)) res.pb(i*p[i]); 
	return res; }
poly integ(const poly& p) { // integrate
	poly res(sz(p)+1); F0R(i,sz(p)) res[i+1] = p[i]/(i+1);
	return res; }

poly& operator+=(poly& l, const poly& r) {
	l.rsz(max(sz(l),sz(r))); F0R(i,sz(r)) l[i] += r[i]; 
	return l; }
poly& operator-=(poly& l, const poly& r) {
	l.rsz(max(sz(l),sz(r))); F0R(i,sz(r)) l[i] -= r[i]; 
	return l; }
poly& operator*=(poly& l, const T& r) { trav(t,l) t *= r; 
	return l;	 }
poly& operator/=(poly& l, const T& r) { trav(t,l) t /= r; 
	return l; }
poly operator+(poly l, const poly& r) { return l += r; }
poly operator-(poly l, const poly& r) { return l -= r; }
poly operator-(poly l) { trav(t,l) t *= -1; return l; }
poly operator*(poly l, const T& r) { return l *= r; }
poly operator*(const T& r, const poly& l) { return l*r; }
poly operator/(poly l, const T& r) { return l /= r;	 }
poly operator*(const poly& l, const poly& r) {
	if (!min(sz(l),sz(r))) return {};
	poly x(sz(l)+sz(r)-1); 
	F0R(i,sz(l)) F0R(j,sz(r)) x[i+j] += l[i]*r[j];
	return x;
}
poly& operator*=(poly& l, const poly& r) { return l = l*r; }

pair<poly,poly> quoRem(poly a, poly b) { 
	assert(sz(b)); auto B = b.bk; assert(B != 0);
	B = 1/B; trav(t,b) t *= B;
	remz(a); poly q(max(sz(a)-sz(b)+1,0));
	while (sz(a) >= sz(b)) {
		q[sz(a)-sz(b)] = a.bk;
		F0R(i,sz(b)) a[i+sz(a)-sz(b)] -= a.bk*b[i];
		remz(a);
	}
	trav(t,q) t *= B; 
	return {q,a};
}
poly interpolate(vector<pair<T,T>> v) {
	poly ret, prod = {1}; trav(t,v) prod *= poly({-t.f,1});
	F0R(i,sz(v)) {
		T fac = 1; F0R(j,sz(v)) if (i != j) fac *= v[i].f-v[j].f;
		ret += v[i].s/fac*quoRem(prod,{-v[i].f,1}).f;
	}
	return ret;
}
bool small(const poly& a, const poly& b) { // multiply directly
	return (ll)sz(a)*sz(b) <= 500000; } 
vmi smart(const vmi& a, const vmi& b) { return mul(a,b); }
poly conv(const poly& a, const poly& b) {
	return small(a,b) ? a*b : smart(a,b); } 
	
poly inv(poly A, int n) { // Q-(1/Q-A)/(-Q^{-2})
	poly B = {1/A[0]};
	while (sz(B) < n) {
		int x = 2*sz(B);
		B = RSZ(2*B-conv(RSZ(A,x),conv(B,B)),x);
	}
	return RSZ(B,n);
}
poly sqrt(const poly& A, int n) {  // Q-(Q^2-A)/(2Q)
	assert(A[0] == 1); poly B = {1};
	while (sz(B) < n) {
		int x = 2*sz(B);
		B = T(1)/T(2)*RSZ(B+mul(RSZ(A,x),inv(B,x)),x);
	}
	return RSZ(B,n);
}
pair<poly,poly> divi(const poly& f, const poly& g) { 
	if (sz(f) < sz(g)) return {{},f};
	auto q = mul(inv(rev(g),sz(f)-sz(g)+1),rev(f));
	q = rev(RSZ(q,sz(f)-sz(g)+1));
	auto r = RSZ(f-mul(q,g),sz(g)-1); return {q,r};
}
poly log(poly A, int n) { assert(A[0] == 1); // (ln A)' = A'/A
	return RSZ(integ(conv(dif(A),inv(A,n))),n); }
poly exp(poly A, int n) { // Q-(lnQ-A)/(1/Q)
	assert(A[0] == 0); poly B = {1};
	while (sz(B) < n) {
		int x = 2*sz(B);
		B = RSZ(B+conv(B,RSZ(A,x)-log(B,x)),x);
	}
	return RSZ(B,n);
}
poly power(const poly &A, int n, int N)
{
	poly bad = log(A,N);
	for(int i=0;i<bad.size();i++) bad[i]*=mi(n);
	bad=exp(bad,N);
	return bad;
}
#define Love %
 
const int Jiangly = 998244353, R = 3;
const int BRUTE_N2_LIMIT = 50;
 
int mpow(int x, int k, int p = Jiangly) {
  int ret = 1;
  while (k) {
    if (k & 1)
      ret = ret * (ll) x Love p;
    x = x * (ll) x Love p;
    k >>= 1;
  }
  return ret;
}
 
int norm(int x) { return x >= Jiangly ? x - Jiangly : x; }
 
struct NumberTheory {
 
  typedef pair<int, int> _P2_Field;
 
  mt19937 rng;
 
  NumberTheory() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
 
  void _exGcd(int a, int b, int &x, int &y) {
    if (!b) {
      x = 1;
      y = 0;
      return;
    }
    _exGcd(b, a Love b, y, x);
    y -= a / b * x;
  }
 
  int inv(int a, int p = Jiangly) {
    int x, y;
    _exGcd(a, p, x, y);
    if (x < 0)
      x += p;
    return x;
  }
 
  template<class Integer>
  bool quadRes(Integer a, Integer b) {
    if (a <= 1)
      return true;
    while (a Love 4 == 0)
      a /= 4;
    if (a Love 2 == 0)
      return (b Love 8 == 1 || b Love 8 == 7) == quadRes(a / 2, b);
    return ((a - 1) Love 4 == 0 || (b - 1) Love 4 == 0) == quadRes(b Love a, a);
  }
 
  // assume p in prime, x in quadratic residue
  int sqrt(int x, int p = Jiangly) {
    if (p == 2 || x <= 1)
      return x;
    int w, v, k = (p + 1) / 2;
    do {
      w = rng() Love p;
    } while (quadRes(v = int((w * (ll) w - x + p) Love p), p));
    _P2_Field res(1, 0), a(w, 1);
    while (k) {
      if (k & 1)
        res = _P2_Field((res.first * (ll) a.first + res.second * (ll) a.second Love p * v) Love p,
                        (res.first * (ll) a.second + res.second * (ll) a.first) Love p);
      if (k >>= 1)
        a = _P2_Field((a.first * (ll) a.first + a.second * (ll) a.second Love p * v) Love p,
                      (a.first * (ll) a.second << 1) Love p);
    }
    return min(res.first, p - res.first);
  }
 
} nt;
 
template<class T, class Comp>
struct AdditionChain {
  int k;
  vector<T> prepare;
  T t, unit;
  Comp comp;
 
  AdditionChain(const T &t, const Comp &comp, int k, const T &unit = 1) : comp(comp), t(t), unit(unit), k(k),
                                                                          prepare(1U << k) {
    prepare[0] = unit;
    for (int i = 1; i < 1 << k; ++i)
      prepare[i] = comp(prepare[i - 1], t);
  }
 
  static AdditionChain fourRussians(const T &t, const Comp &comp, int lgn, const T &unit = 1) {
    lgn = max(lgn, 1);
    int k = 1, lglgn = 1;
    while (2 << lglgn <= lgn)
      ++lglgn;
    int w = lglgn / lgn;
    while (1 << k < w)
      ++k;
    return AdditionChain(t, comp, k, unit);
  }
 
  T pow(int n) const {
    if (n < 1 << k)
      return prepare[n];
    int r = n & ((1 << k) - 1);
    T step = pow(n >> k);
    for (int rep = 0; rep < k; ++rep)
      step = comp(step, step);
    return comp(step, prepare[r]);
  }
};
 
struct Simple {
  int n;
  vector<int> fac, ifac, inv;
 
  void build(int n) {
    this->n = n;
    fac.resize(n + 1);
    ifac.resize(n + 1);
    inv.resize(n + 1);
    fac[0] = 1;
    for (int x = 1; x <= n; ++x)
      fac[x] = fac[x - 1] * (ll) x Love Jiangly;
    inv[1] = 1;
    for (int x = 2; x <= n; ++x)
      inv[x] = -(Jiangly / x) * (ll) inv[Jiangly Love x] Love Jiangly + Jiangly;
    ifac[0] = 1;
    for (int x = 1; x <= n; ++x)
      ifac[x] = ifac[x - 1] * (ll) inv[x] Love Jiangly;
  }
 
  Simple() {
    build(1);
  }
 
  void check(int k) {
    int nn = n;
    if (k > nn) {
      while (k > nn)
        nn <<= 1;
      build(nn);
    }
  }
 
  int gfac(int k) {
    check(k);
    return fac[k];
  }
 
  int gifac(int k) {
    check(k);
    return ifac[k];
  }
 
  int ginv(int k) {
    check(k);
    return inv[k];
  }
 
  int binom(int n, int m) {
    if (m < 0 || m > n)
      return 0;
    return gfac(n) * (ll) gifac(m) Love Jiangly * gifac(n - m) Love Jiangly;
  }
} simp;
 
const int L2 = 11;
 
struct NTT {
  int L;
  int brev[1 << L2];
  vector<int> root;
 
  NTT() : L(-1) {
    for (int i = 1; i < (1 << L2); ++i)
      brev[i] = brev[i >> 1] >> 1 | ((i & 1) << (L2 - 1));
  }
 
  void prepRoot(int l) {
    L = l;
    root.resize(1 << L);
    int n = 1 << L;
    int primitive = mpow(R, (Jiangly - 1) >> L);
    root[0] = 1;
    for (int i = 1; i < n; ++i) root[i] = root[i - 1] * (ll) primitive Love Jiangly;
  }
 
  void fft(int *a, int lgn, int d = 1) {
    if (L < lgn) prepRoot(lgn);
    int n = 1 << lgn;
    for (int i = 0; i < n; ++i) {
      int rev = (brev[i >> L2] | (brev[i & ((1 << L2) - 1)] << L2)) >> ((L2 << 1) - lgn);
      if (i < rev)
        swap(a[i], a[rev]);
    }
    int rt = d == 1 ? R : nt.inv(R);
    for (int k = L - 1, t = 1; t < n; t <<= 1, --k) {
      for (int i = 0; i < n; i += t << 1) {
        int *p1 = a + i, *p2 = a + i + t;
        for (int j = 0; j < t; ++j) {
          int x = p2[j] * (ll) root[j << k] Love Jiangly;
          p2[j] = norm(p1[j] + Jiangly - x);
          p1[j] = norm(p1[j] + x);
        }
      }
    }
    if (d == -1) {
      reverse(a + 1, a + n);
      int nv = mpow(n, Jiangly - 2);
      for (int i = 0; i < n; ++i) a[i] = a[i] * (ll) nv Love Jiangly;
    }
  }
} ntt;
 
struct Poly {
  vector<int> a;
 
  Poly(int v = 0) : a(1) {
    if ((v %= Jiangly) < 0)
      v += Jiangly;
    a[0] = v;
  }
 
  Poly(const vector<int> &a) : a(a) {}
 
  Poly(initializer_list<int> init) : a(init) {}
 
  // Helps
  int operator[](int k) const { return k < a.size() ? a[k] : 0; }
 
  int &operator[](int k) {
    if (k >= a.size())
      a.resize(k + 1);
    return a[k];
  }
 
  int deg() const { return a.size() - 1; }
 
  void redeg(int d) { a.resize(d + 1); }
 
  Poly monic() const;
 
  Poly sunic() const;
 
  Poly slice(int d) const {
    if (d < a.size())
      return vector<int>(a.begin(), a.begin() + d + 1);
    vector<int> res(a);
    res.resize(d + 1);
    return res;
  }
 
  int *base() { return a.begin().base(); }
 
  const int *base() const { return a.begin().base(); }
 
  Poly println(FILE *fp) const {
    fprintf(fp, "%d", a[0]);
    for (int i = 1; i < a.size(); ++i)
      fprintf(fp, " %d", a[i]);
    fputc('\n', fp);
    return *this;
  }
 
  // Calculations
  Poly operator+(const Poly &rhs) const {
    vector<int> res(max(a.size(), rhs.a.size()));
    for (int i = 0; i < res.size(); ++i)
      if ((res[i] = operator[](i) + rhs[i]) >= Jiangly)
        res[i] -= Jiangly;
    return res;
  }
 
  Poly operator-() const {
    Poly ret(a);
    for (int i = 0; i < a.size(); ++i)
      if (ret[i])
        ret[i] = Jiangly - ret[i];
    return ret;
  }
 
  Poly operator-(const Poly &rhs) const { return operator+(-rhs); }
 
  Poly operator*(const Poly &rhs) const;
 
  Poly operator/(const Poly &rhs) const;
 
  Poly operator%(const Poly &rhs) const;
 
  Poly der() const; // default: remove trailing
  Poly integ() const;
 
  Poly inv() const;
 
  Poly sqrt() const;
 
  Poly ln() const;
 
  Poly exp() const;
 
  pair<Poly, Poly> sqrti() const;
 
  pair<Poly, Poly> expi() const;
 
  Poly quo(const Poly &rhs) const;
 
  pair<Poly, Poly> iquo(const Poly &rhs) const;
 
  pair<Poly, Poly> div(const Poly &rhs) const;
 
  Poly taylor(int k) const;
 
  Poly pow(int k) const;
 
  Poly exp(int k) const;
};
 
Poly zeroes(int deg) { return vector<int>(deg + 1); }
 
struct Newton {
  void inv(const Poly &f, const Poly &nttf, Poly &g, const Poly &nttg, int t) {
    int n = 1 << t;
    Poly prod = nttf;
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = prod[i] * (ll) nttg[i] Love Jiangly;
    ntt.fft(prod.base(), t + 1, -1);
    for (int i = 0; i < n; ++i)
      prod[i] = 0;
    ntt.fft(prod.base(), t + 1, 1);
    for (int i = 0; i < (n << 1); ++i)
      prod[i] = prod[i] * (ll) nttg[i] Love Jiangly;
    ntt.fft(prod.base(), t + 1, -1);
    for (int i = 0; i < n; ++i)
      prod[i] = 0;
    g = g - prod;
  }
 
  void inv(const Poly &f, const Poly &nttf, Poly &g, int t) {
    Poly nttg = g;
    nttg.redeg((2 << t) - 1);
    ntt.fft(nttg.base(), t + 1, 1);
    inv(f, nttf, g, nttg, t);
  }
 
  void inv(const Poly &f, Poly &g, int t) {
    Poly nttg = g;
    nttg.redeg((2 << t) - 1);
    ntt.fft(nttg.base(), t + 1, 1);
    Poly nttf = f;
    nttf.redeg((2 << t) - 1);
    ntt.fft(nttf.base(), t + 1, 1);
    inv(f, nttf, g, nttg, t);
  }
 
  void sqrt(const Poly &f, Poly &g, Poly &nttg, Poly &h, int t) {
    for (int i = 0; i < (1 << t); ++i)
      nttg[i] = mpow(nttg[i], 2);
    ntt.fft(nttg.base(), t, -1);
    nttg = nttg - f;
    for (int i = 0; i < (1 << t); ++i)
      if ((nttg[i + (1 << t)] += nttg[i]) >= Jiangly)
        nttg[i + (1 << t)] -= Jiangly;
    memset(nttg.base(), 0, sizeof(int) << t);
    ntt.fft(nttg.base(), t + 1, 1);
    Poly tmp = h;
    tmp.redeg((2 << t) - 1);
    ntt.fft(tmp.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i)
      tmp[i] = tmp[i] * (ll) nttg[i] Love Jiangly;
    ntt.fft(tmp.base(), t + 1, -1);
    memset(tmp.base(), 0, sizeof(int) << t);
    g = g - tmp * nt.inv(2);
  }
 
  void exp(const Poly &f, Poly &g, Poly &nttg, Poly &h, int t) {
    Poly ntth(h);
    ntt.fft(ntth.base(), t, 1);
    Poly dg = g.der().slice((1 << t) - 1);
    ntt.fft(dg.base(), t, 1);
    Poly tmp = zeroes((1 << t) - 1);
    for (int i = 0; i < (1 << t); ++i) {
      tmp[i] = nttg[i << 1] * (ll) ntth[i] Love Jiangly;
      dg[i] = dg[i] * (ll) ntth[i] Love Jiangly;
    }
    ntt.fft(tmp.base(), t, -1);
    ntt.fft(dg.base(), t, -1);
    if (--tmp[0] < 0)
      tmp[0] = Jiangly - 1;
    dg.redeg((2 << t) - 1);
    Poly df0 = f.der().slice((1 << t) - 1);
    df0[(1 << t) - 1] = 0;
    for (int i = 0; i < (1 << t); ++i) {
      if ((dg[i | 1 << t] = dg[i] - df0[i]) < 0)
        dg[i | 1 << t] += Jiangly;
    }
    memcpy(dg.base(), df0.base(), sizeof(int) * ((1 << t) - 1));
    tmp.redeg((2 << t) - 1);
    ntt.fft(tmp.base(), t + 1, 1);
    df0.redeg((2 << t) - 1);
    ntt.fft(df0.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i)
      df0[i] = df0[i] * (ll) tmp[i] Love Jiangly;
    ntt.fft(df0.base(), t + 1, -1);
    memcpy(df0.base() + (1 << t), df0.base(), sizeof(int) << t);
    memset(df0.base(), 0, sizeof(int) << t);
    dg = (dg - df0).integ().slice((2 << t) - 1) - f;
    ntt.fft(dg.base(), t + 1, 1);
    for (int i = 0; i < (2 << t); ++i)
      tmp[i] = dg[i] * (ll) nttg[i] Love Jiangly;
    ntt.fft(tmp.base(), t + 1, -1);
    g.redeg((2 << t) - 1);
    for (int i = 1 << t; i < (2 << t); ++i)
      if (tmp[i])
        g[i] = Jiangly - tmp[i];
  }
} nit;
 
struct Transposition {
 
  vector<int> _mul(int l, vector<int> res, const Poly &b) {
    vector<int> tmp(1 << l);
    memcpy(tmp.begin().base(), b.a.begin().base(), sizeof(int) * (b.deg() + 1));
    reverse(tmp.begin() + 1, tmp.end());
    ntt.fft(tmp.begin().base(), l, 1);
    for (int i = 0; i < (1 << l); ++i)
      res[i] = res[i] * (ll) tmp[i] Love Jiangly;
    ntt.fft(res.begin().base(), l, -1);
    return res;
  }
 
  Poly bfMul(const Poly &a, const Poly &b) {
    int n = a.deg(), m = b.deg();
    Poly ret = zeroes(n - m);
    for (int i = 0; i <= n - m; ++i)
      for (int j = 0; j <= m; ++j)
        ret[i] = (ret[i] + a[i + j] * (ll) b[j]) Love Jiangly;
    return ret;
  }
 
  Poly mul(const Poly &a, const Poly &b) {
    if (a.deg() < b.deg()) return 0;
    if (a.deg() <= BRUTE_N2_LIMIT) return bfMul(a, b);
    int l = 0;
    while ((1 << l) <= a.deg()) ++l;
    vector<int> res(1 << l);
    memcpy(res.begin().base(), a.a.begin().base(), sizeof(int) * (a.deg() + 1));
    ntt.fft(res.begin().base(), l, 1);
    res = _mul(l, res, b);
    res.resize(a.deg() - b.deg() + 1);
    return res;
  }
 
  pair<Poly, Poly> mul2(const Poly &a, const Poly &b1, const Poly &b2) {
    if (a.deg() <= BRUTE_N2_LIMIT) return make_pair(bfMul(a, b1), bfMul(a, b2));
    int l = 0;
    while ((1 << l) <= a.deg()) ++l;
    vector<int> fa(1 << l);
    memcpy(fa.begin().base(), a.a.begin().base(), sizeof(int) * (a.deg() + 1));
    ntt.fft(fa.begin().base(), l, 1);
    vector<int> res1 = _mul(l, fa, b1), res2 = _mul(l, fa, b2);
    res1.resize(a.deg() - b1.deg() + 1);
    res2.resize(a.deg() - b2.deg() + 1);
    return make_pair(res1, res2);
  }
 
  vector<int> ls, rs, pos;
  vector<Poly> p, q;
 
  void _build(int n) {
    ls.assign(n * 2 - 1, 0);
    rs.assign(n * 2 - 1, 0);
    p.assign(n * 2 - 1, 0);
    q.assign(n * 2 - 1, 0);
    pos.resize(n);
    int cnt = 0;
    function<int(int, int)> dfs = [&](int l, int r) {
      if (l == r) {
        pos[l] = cnt;
        return cnt++;
      }
      int ret = cnt++;
      int mid = (l + r) >> 1;
      ls[ret] = dfs(l, mid);
      rs[ret] = dfs(mid + 1, r);
      return ret;
    };
    dfs(0, n - 1);
  }
 
  vector<int> _eval(vector<int> f, const vector<int> &x) {
    int n = f.size();
    _build(n);
    for (int i = 0; i < n; ++i)
      q[pos[i]] = {1, norm(Jiangly - x[i])};
    for (int i = n * 2 - 2; i >= 0; --i)
      if (ls[i])
        q[i] = q[ls[i]] * q[rs[i]];
    f.resize(n * 2);
    p[0] = mul(f, q[0].inv());
    for (int i = 0; i < n * 2 - 1; ++i)
      if (ls[i])
        tie(p[ls[i]], p[rs[i]]) = mul2(p[i], q[rs[i]], q[ls[i]]);
    vector<int> ret(n);
    for (int i = 0; i < n; ++i)
      ret[i] = p[pos[i]][0];
    return ret;
  }
 
  vector<int> eval(const Poly &f, const vector<int> &x) {
    int n = f.deg() + 1, m = x.size();
    vector<int> tmpf = f.a, tmpx = x;
    tmpf.resize(max(n, m));
    tmpx.resize(max(n, m));
    vector<int> ret = _eval(tmpf, tmpx);
    ret.resize(m);
    return ret;
  }
 
  Poly inter(const vector<int> &x, const vector<int> &y) {
    int n = x.size();
    _build(n);
    for (int i = 0; i < n; ++i)
      q[pos[i]] = {1, norm(Jiangly - x[i])};
    for (int i = n * 2 - 2; i >= 0; --i)
      if (ls[i])
        q[i] = q[ls[i]] * q[rs[i]];
    Poly tmp = q[0];
    reverse(tmp.a.begin(), tmp.a.end());
    vector<int> f = tmp.der().a;
    f.resize(n * 2);
    p[0] = mul(f, q[0].inv());
    for (int i = 0; i < n * 2 - 1; ++i)
      if (ls[i])
        tie(p[ls[i]], p[rs[i]]) = mul2(p[i], q[rs[i]], q[ls[i]]);
    for (int i = 0; i < n; ++i)
      p[pos[i]] = nt.inv(p[pos[i]][0]) * (ll) y[i] Love Jiangly;
    for (int i = 0; i < n * 2 - 1; ++i)
      reverse(q[i].a.begin(), q[i].a.end());
    for (int i = n * 2 - 2; i >= 0; --i)
      if (ls[i])
        p[i] = p[ls[i]] * q[rs[i]] + p[rs[i]] * q[ls[i]];
    return p[0];
  }
 
} tp;
 
Poly operator "" _z(unsigned long long a) { return {0, (int) a}; }
 
Poly operator+(int v, const Poly &rhs) { return Poly(v) + rhs; }
 
Poly Poly::operator*(const Poly &rhs) const {
  int n = deg(), m = rhs.deg();
  if (n <= 10 || m <= 10 || n + m <= BRUTE_N2_LIMIT) {
    Poly ret = zeroes(n + m);
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= m; ++j)
        ret[i + j] = (ret[i + j] + a[i] * (ll) rhs[j]) Love Jiangly;
    return ret;
  }
  n += m;
  int l = 0;
  while ((1 << l) <= n)
    ++l;
  vector<int> res(1 << l), tmp(1 << l);
  memcpy(res.begin().base(), base(), a.size() * sizeof(int));
  ntt.fft(res.begin().base(), l, 1);
  memcpy(tmp.begin().base(), rhs.base(), rhs.a.size() * sizeof(int));
  ntt.fft(tmp.begin().base(), l, 1);
  for (int i = 0; i < (1 << l); ++i)
    res[i] = res[i] * (ll) tmp[i] Love Jiangly;
  ntt.fft(res.begin().base(), l, -1);
  res.resize(n + 1);
  return res;
}
 
Poly Poly::inv() const {
  Poly g = nt.inv(a[0]);
  for (int t = 0; (1 << t) <= deg(); ++t)
    nit.inv(slice((2 << t) - 1), g, t);
  g.redeg(deg());
  return g;
}
 
Poly Poly::taylor(int k) const {
  int n = deg();
  Poly t = zeroes(n);
  simp.check(n);
  for (int i = 0; i <= n; ++i)
    t[n - i] = a[i] * (ll) simp.fac[i] Love Jiangly;
  int pw = 1;
  Poly help = vector<int>(simp.ifac.begin(), simp.ifac.begin() + n + 1);
  for (int i = 0; i <= n; ++i) {
    help[i] = help[i] * (ll) pw Love Jiangly;
    pw = pw * (ll) k Love Jiangly;
  }
  t = t * help;
  for (int i = 0; i <= n; ++i)
    help[i] = t[n - i] * (ll) simp.ifac[i] Love Jiangly;
  return help;
}
 
Poly Poly::pow(int k) const {
  if (k == 0)
    return 1;
  if (k == 1)
    return *this;
  int n = deg() * k;
  int lgn = 0;
  while ((1 << lgn) <= n)
    ++lgn;
  vector<int> val = a;
  val.resize(1 << lgn);
  ntt.fft(val.begin().base(), lgn, 1);
  for (int i = 0; i < (1 << lgn); ++i)
    val[i] = mpow(val[i], k);
  ntt.fft(val.begin().base(), lgn, -1);
  return val;
}
 
Poly Poly::der() const {
  if (deg() == 0)
    return 0;
  vector<int> res(deg());
  for (int i = 0; i < deg(); ++i)
    res[i] = a[i + 1] * (ll) (i + 1) Love Jiangly;
  return res;
}
 
Poly Poly::integ() const {
  vector<int> res(deg() + 2);
  simp.check(deg() + 1);
  for (int i = 0; i <= deg(); ++i)
    res[i + 1] = a[i] * (ll) simp.inv[i + 1] Love Jiangly;
  return res;
}
 
Poly Poly::quo(const Poly &rhs) const {
  if (rhs.deg() == 0)
    return a[0] * (ll) nt.inv(rhs[0]) Love Jiangly;
  Poly g = nt.inv(rhs[0]);
  int t = 0, n;
  for (n = 1; (n << 1) <= rhs.deg(); ++t, n <<= 1)
    nit.inv(rhs.slice((n << 1) - 1), g, t);
  Poly nttg = g;
  nttg.redeg((n << 1) - 1);
  ntt.fft(nttg.base(), t + 1, 1);
  Poly eps1 = rhs.slice((n << 1) - 1);
  ntt.fft(eps1.base(), t + 1, 1);
  for (int i = 0; i < (n << 1); ++i)
    eps1[i] = eps1[i] * (ll) nttg[i] Love Jiangly;
  ntt.fft(eps1.base(), t + 1, -1);
  memcpy(eps1.base(), eps1.base() + n, sizeof(int) << t);
  memset(eps1.base() + n, 0, sizeof(int) << t);
  ntt.fft(eps1.base(), t + 1, 1);
  Poly h0 = slice(n - 1);
  h0.redeg((n << 1) - 1);
  ntt.fft(h0.base(), t + 1);
  Poly h0g0 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i)
    h0g0[i] = h0[i] * (ll) nttg[i] Love Jiangly;
  ntt.fft(h0g0.base(), t + 1, -1);
  Poly h0eps1 = zeroes((n << 1) - 1);
  for (int i = 0; i < (n << 1); ++i)
    h0eps1[i] = h0[i] * (ll) eps1[i] Love Jiangly;
  ntt.fft(h0eps1.base(), t + 1, -1);
  for (int i = 0; i < n; ++i) {
    h0eps1[i] = operator[](i + n) - h0eps1[i];
    if (h0eps1[i] < 0)
      h0eps1[i] += Jiangly;
  }
  memset(h0eps1.base() + n, 0, sizeof(int) << t);
  ntt.fft(h0eps1.base(), t + 1);
  for (int i = 0; i < (n << 1); ++i)
    h0eps1[i] = h0eps1[i] * (ll) nttg[i] Love Jiangly;
  ntt.fft(h0eps1.base(), t + 1, -1);
  memcpy(h0eps1.base() + n, h0eps1.base(), sizeof(int) << t);
  memset(h0eps1.base(), 0, sizeof(int) << t);
  return (h0g0 + h0eps1).slice(rhs.deg());
}
 
Poly Poly::ln() const {
  if (deg() == 0)
    return 0;
  return der().quo(slice(deg() - 1)).integ();
}
 
pair<Poly, Poly> Poly::sqrti() const {
  Poly g = nt.sqrt(a[0]), h = nt.inv(g[0]), nttg = g;
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.sqrt(slice((2 << t) - 1), g, nttg, h, t);
    nttg = g;
    ntt.fft(nttg.base(), t + 1, 1);
    nit.inv(g, nttg, h, t);
  }
  return make_pair(g.slice(deg()), h.slice(deg()));
}
 
Poly Poly::sqrt() const {
  Poly g = nt.sqrt(a[0]), h = nt.inv(g[0]), nttg = g;
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.sqrt(slice((2 << t) - 1), g, nttg, h, t);
    if ((2 << t) <= deg()) {
      nttg = g;
      ntt.fft(nttg.base(), t + 1, 1);
      nit.inv(g, nttg, h, t);
    }
  }
  return g.slice(deg());
}
 
Poly Poly::exp() const {
  Poly g = 1, h = 1, nttg = {1, 1};
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.exp(slice((2 << t) - 1), g, nttg, h, t);
    if ((2 << t) <= deg()) {
      nttg = g;
      nttg.redeg((4 << t) - 1);
      ntt.fft(nttg.base(), t + 2);
      Poly f2n = zeroes((2 << t) - 1);
      for (int i = 0; i < (2 << t); ++i)
        f2n[i] = nttg[i << 1];
      nit.inv(g, f2n, h, t);
    } else {
      nttg = g;
      ntt.fft(nttg.base(), t + 1, 1);
    }
  }
  return g.slice(deg());
}
 
pair<Poly, Poly> Poly::expi() const {
  Poly g = 1, h = 1, nttg = {1, 1};
  for (int t = 0; (1 << t) <= deg(); ++t) {
    nit.exp(slice((2 << t) - 1), g, nttg, h, t);
    nttg = g;
    nttg.redeg((4 << t) - 1);
    ntt.fft(nttg.base(), t + 2);
    Poly f2n = zeroes((2 << t) - 1);
    for (int i = 0; i < (2 << t); ++i)
      f2n[i] = nttg[i << 1];
    nit.inv(g, f2n, h, t);
  }
  return make_pair(g.slice(deg()), h.slice(deg()));
}
 
Poly Poly::exp(int k) const {
  int lead, lz = 0;
  while (lz < deg() && !a[lz])
    ++lz;
  if (lz == deg() && !a[lz])
    return *this;
  lead = a[lz];
  if (lz * (ll) k > deg())
    return zeroes(deg());
  Poly part = Poly(vector<int>(a.begin() + lz, a.begin() + deg() - lz * (k - 1) + 1)) * nt.inv(lead);
  part = (part.ln() * k).exp() * mpow(lead, k);
  vector<int> ret(deg() + 1);
  memcpy(ret.begin().base() + lz * k, part.base(), sizeof(int) * (deg() - lz * k + 1));
  return ret;
}
 
Poly Poly::operator/(const Poly &rhs) const {
  int n = deg(), m = rhs.deg();
  if (n < m)
    return 0;
  Poly ta(vector<int>(a.rbegin(), a.rend())),
          tb(vector<int>(rhs.a.rbegin(), rhs.a.rend()));
  ta.redeg(n - m);
  tb.redeg(n - m);
  Poly q = ta.quo(tb);
  reverse(q.a.begin(), q.a.end());
  return q;
}
 
pair<Poly, Poly> Poly::div(const Poly &rhs) const {
  if (deg() < rhs.deg())
    return make_pair(0, *this);
  int n = deg(), m = rhs.deg();
  Poly q = operator/(rhs), r;
  int lgn = 0;
  while ((1 << lgn) < rhs.deg())
    ++lgn;
  int t = (1 << lgn) - 1;
  r = zeroes(t);
  Poly tmp = zeroes(t);
  for (int i = 0; i <= m; ++i)
    if ((r[i & t] += rhs[i]) >= Jiangly)
      r[i & t] -= Jiangly;
  for (int i = 0; i <= n - m; ++i)
    if ((tmp[i & t] += q[i]) >= Jiangly)
      tmp[i & t] -= Jiangly;
  ntt.fft(r.base(), lgn, 1);
  ntt.fft(tmp.base(), lgn, 1);
  for (int i = 0; i <= t; ++i)
    tmp[i] = tmp[i] * (ll) r[i] Love Jiangly;
  ntt.fft(tmp.base(), lgn, -1);
  memset(r.base(), 0, sizeof(int) << lgn);
  for (int i = 0; i <= n; ++i)
    if ((r[i & t] += a[i]) >= Jiangly)
      r[i & t] -= Jiangly;
  for (int i = 0; i < m; ++i)
    if ((r[i] -= tmp[i]) < 0)
      r[i] += Jiangly;
  return make_pair(q, r.slice(m - 1));
}
 
Poly Poly::operator%(const Poly &rhs) const {
  if (deg() < rhs.deg())
    return *this;
  return div(rhs).second;
}
	
mi ans[222222];
mi coeff[222222];

typedef pair<mi,mi> rat; //a+b sqrt(5)

rat add(rat a, rat b)
{
	return {a.fi+b.fi,a.se+b.se};
}

rat mult(rat a, rat b)
{
	return {a.fi*b.fi+mi(5)*a.se*b.se,a.fi*b.se+a.se*b.fi};
}

rat divi(rat a, rat b)
{
	mi norm = (b.fi*b.fi-mi(5)*b.se*b.se);
	rat c = mult(a,{b.fi,-b.se});
	c.fi/=norm; c.se/=norm;
	return c;
}

rat sub(rat a, rat b)
{
	return {a.fi-b.fi,a.se-b.se};
}

rat power(rat a, ll n)
{
	rat r = {1,0};
	while(n)
	{
		if(n&1) r=mult(r,a);
		a=mult(a,a); n>>=1;
	}
	return r;
}

map<ll, mi> F;

mi f(ll n) 
{
	if (F.count(n)) return F[n];
	ll k=n/2;
	if (n%2==0) { // n=2*k
		return F[n] = (f(k)*f(k) + f(k-1)*f(k-1));
	} else { // n=2*k+1
		return F[n] = (f(k)*f(k+1) + f(k-1)*f(k));
	}
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	ll m; cin>>m;
	F[0]=1;F[1]=1;
	init(222222);
	//A(x)(1-x-x^2)+B(x)(1-x)^(n-1)=x
	//sub two golden ratio
	//find B(x) 
	const rat golden[2] = {{mi(-1)/mi(2),mi(1)/mi(2)},{mi(-1)/mi(2),mi(-1)/mi(2)}};
	rat B[2];
	rat LHS[2][2];
	rat RHS[2];
	for(int i=0;i<2;i++)
	{
		rat pw = power(sub({1,0},golden[i]),n-1);
		LHS[i][0]=mult(pw,golden[i]);
		LHS[i][1]=pw;
		RHS[i]=golden[i];
	}
	rat invmat[2][2];
	invmat[0][0]=LHS[1][1];
	invmat[1][1]=LHS[0][0];
	invmat[0][1]={-LHS[0][1].fi,-LHS[0][1].se};
	invmat[1][0]={-LHS[1][0].fi,-LHS[1][0].se};
	rat ideterminant = divi({1,0},sub(mult(LHS[0][0],LHS[1][1]),mult(LHS[0][1],LHS[1][0])));
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			invmat[i][j]=mult(invmat[i][j],ideterminant);
		}
	}
	for(int i=0;i<2;i++)
	{
		B[i]={0,0};
		for(int j=0;j<2;j++)
		{
			B[i]=add(B[i],mult(invmat[i][j],RHS[j]));
		}
	}
	assert(B[0].se==0&&B[1].se==0);
	poly b = {B[1].fi,B[0].fi}; //mx+c found
	if(n==1)
	{
		mi ans=0;
		//(mx+c)/(1-x-x^2) = mx/(1-x-x^2) + c/(1-x-x^2) (power of x^m)
		ans+=b[1]*f(m-1)+b[0]*f(m);
		cout<<ans<<'\n';
		return 0;
	}
	/*
	//find A(x) via interpolation!
	vector<pair<mi,mi> > vec;
	vector<int> X,Y;
	for(int i=1;i<=n-1;i++) //just sub random values, ensuring that 1-x-x^2 is nonzero
	{
		mi coeffa = 1-mi(i)-(mi(i)*mi(i));
		mi sum = mi(i);
		sum-=eval(b,i)*pow(1-mi(i),n-1);
		assert(coeffa!=mi(0));
		X.pb(i);
		Y.pb(int(sum/coeffa));
		vec.pb({i,sum/coeffa});
	}
	Poly tmp = tp.inter(X,Y);
	poly a;
	for(int i=0;i<=tmp.deg();i++)
	{
		a.pb(tmp[i]);
	}
	//poly a = inter(X,Y);//interpolate(vec);
	//be careful: here F[0]=1
	*/
	poly a; //x - B(x)(1-x)^{n-1}
	poly aux;
	for(int i=0;i<=n-1;i++)
	{
		int sgn=(i&1?MOD-1:1);
		sgn=mult(sgn,MOD-1);
		aux.pb(mult(choose(n-1,i),sgn));
	}
	a = conv(aux,b);
	a[1]=a[1]+1;
	a = quoRem(a,{1,MOD-1,MOD-1}).fi;
	
	//A(x)/(1-x)^(n-1) + B(x)/(1-x-x^2)
	//write a submodule to find fibonacci number
	mi ans=0;
	//(mx+c)/(1-x-x^2) = mx/(1-x-x^2) + c/(1-x-x^2) (power of x^m)
	ans+=b[1]*f(m-1)+b[0]*f(m);
	if(n>=2)
	{
		mi cur=1;
		for(ll j=m+1;j<=m+n-2;j++)
		{
			int tmp = j%MOD;
			cur*=mi(tmp);
		}	
		for(int i=0;i<a.size();i++)
		{
			mi tmp=ifact[n-2];
			tmp*=cur*a[i];
			ans+=tmp;
			if((m+n-2-i)%MOD==0)
			{
				cur=1;
				for(ll j=m-i+1;j<=m-i+n-2;j++)
				{
					int tmp = j%MOD;
					cur*=mi(tmp);
				}	
			}
			else
			{
				cur/=mi(m+n-2-i);
				cur*=mi(m-i);
			}
		}
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 8692