#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500005
#define int unsigned long long
using std::vector;
typedef vector<int> poly;
const int MOD=998244353;
int iv[N], iiv[N], fac[N], tp;
namespace iobuff{
	const int LEN=1000000;
	char in[LEN+5], out[LEN+5];
	char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
	inline char gc(void)
	{
		return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;
	}
	inline void pc(char c)
	{
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;
	}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void scan(T &x)
	{
		static int f;
		static char c;
		c=gc(), f=1, x=0;
		while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
		while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
		x*=f;
	}
	template<typename T> inline void putint(T x, char div)
	{
		static char s[15];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}
using namespace iobuff;
inline void init(void) { tp=2; iv[0]=iv[1]=iiv[0]=iiv[1]=1, fac[0]=fac[1]=1; }
inline void ext(int x)
{
	for(; tp<=x; ++tp)
	{
		iv[tp]=MOD-1ll*(MOD/tp)*iv[MOD%tp]%MOD;
		iiv[tp]=1ll*iiv[tp-1]*iv[tp]%MOD;
		fac[tp]=1ll*fac[tp-1]*tp%MOD;
	}
}
//inline int mval(int x) { (x>=MOD)&&(x-=MOD); return x; }
inline int mval(int x) { return x>=MOD?x-MOD:x; }
inline void inc(int &x, int a) { x=mval(x+a); }
inline void dec(int &x, int a) { x=mval(MOD+x-a); }
inline int qpow(int x, int p)
{ int ret=1; while(p) { if(p&1) ret=1ll*ret*x%MOD; p>>=1, x=1ll*x*x%MOD; } return ret; }
inline int inv(int x) { return qpow(x, MOD-2); }
namespace Poly{
	namespace Poly_Basic{
		inline void print(const poly &a) { for(int x:a) printf("%d ", x); puts(""); }
		inline void printbuff(const poly &a) { for(int x:a) putint(x, ' '); pc('\n'); }
		inline poly to_poly(int *a, int n) { poly ret; ret.resize(n); memcpy((int*)&ret[0], a, sizeof(int)*n); return ret; }
		inline poly slice(const poly &a, int s, int t)
		{ poly ret(t-s); memcpy((int*)&ret[0], (int*)&a[s], sizeof(int)*(t-s)); return ret; }
		inline poly add(const poly &a, const poly &b)
		{
			poly ret(std::max(a.size(), b.size()));
			for(int i=0; i<ret.size(); ++i) ret[i]=mval((i<a.size()?a[i]:0)+(i<b.size()?b[i]:0));
			return ret;
		}
		inline void add_to(poly &a, const poly &b)
		{
			if(a.size()<b.size()) a.resize(b.size());
			for(int i=0; i<b.size(); ++i) inc(a[i], b[i]);
		}
		inline poly neg(poly a)
		{
			for(int i=0; i<a.size(); ++i) a[i]=MOD-a[i];
			return a;
		}
		inline poly mul(poly a, int x)
		{
			for(int i=0; i<a.size(); ++i) a[i]=1ll*a[i]*x%MOD;
			return a;
		}
		inline void mul_val(poly &a, int x)
		{
			for(int i=0; i<a.size(); ++i) a[i]=1ll*a[i]*x%MOD;
		}
		inline poly deri(poly a)
		{
			for(int i=0; i<a.size()-1; ++i) a[i]=1ll*a[i+1]*(i+1)%MOD;
			a.pop_back();
			return a;
		}
		inline poly intg(poly a)
		{
			a.push_back(0);
			if(tp<a.size()) ext(a.size());
			for(int i=a.size()-1; i; --i) a[i]=1ll*iv[i]*a[i-1]%MOD;
			a[0]=0;
			return a;
		}
		inline int calc(const poly &a, int p)
		{
			int ret=0;
			for(int i=0, x=1; i<a.size(); ++i, x=1ll*x*p%MOD) inc(ret, 1ll*a[i]*x%MOD);
			return ret;
		}
	}
	using namespace Poly_Basic;
	namespace NTT{
		const int g=3;
		int A[N], B[N], C[N], rev[N], wn[N], up=1;
		inline int glim(int n)
		{
			int l=0;
			while(n) n>>=1, ++l;
			return l;
		}
		inline void init(int l)
		{
			for(int i=1; i<(1<<l); ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
			for(int i=up; i<(1<<l); i<<=1)
			{
				wn[i]=1;
				int mw=qpow(g, (MOD-1)/(i<<1));
				for(int j=1; j<i; ++j) wn[i+j]=1ll*wn[i+j-1]*mw%MOD;
			}
			if((1<<l)>up) up=(1<<l);
		}
		inline void ntt(int *f, int n, int mod)
		{
//			tt1-=clock();
//			tt+=n*__builtin_ctz(n);
			for(int i=0; i<n; ++i) if(i<rev[i]) std::swap(f[i], f[rev[i]]);
			for(int len=2; len<=n; len<<=1)
			{
				int c=len>>1;
				for(int i=0; i<n; i+=len) for(int j=i; j<i+c; ++j)
				{
					int x=f[j], y=1ll*f[j+c]*wn[c+j-i]%MOD;
					f[j]=mval(x+y), f[j+c]=mval(MOD+x-y);
//					f[j]=mval(x+y), f[j+c]=mval(MOD+x-y);
				}
			}
//			for(int i=0; i<n; ++i) f[i]%=MOD;
			if(mod)
			{
				std::reverse(f+1, f+n);
				int iv=inv(n);
				for(int i=0; i<n; ++i) f[i]=1ll*f[i]*iv%MOD;
			}
//			tt1+=clock();
		}
		template <class _T, class _T1, class _T2> inline void mul(const _T &a, const _T1 &b, _T2 &c, int n, int m)
		{
			int l=glim(n+m);
			init(l);
			memcpy(A, (int*)&a[0], sizeof(int)*(n+1));
			memcpy(B, (int*)&b[0], sizeof(int)*(m+1));
			std::fill(A+n+1, A+(1<<l)+1, 0);
			std::fill(B+m+1, B+(1<<l)+1, 0);
			ntt(A, (1<<l), 0), ntt(B, (1<<l), 0);
			for(int i=0; i<(1<<l); ++i) C[i]=1ll*A[i]*B[i]%MOD;
			ntt(C, (1<<l), 1);
			memcpy((int*)&c[0], C, sizeof(int)*(n+m+1));
		}
		inline poly mul(const poly &a, const poly &b)
		{
			if(!a.size()||!b.size()) return poly(0);
//			puts("in");
			poly ret(a.size()+b.size()-1);
			mul(a, b, ret, a.size()-1, b.size()-1);
//			puts("out");
			return ret;
		}
	}
	using NTT::init;
	using NTT::ntt;
	using NTT::glim;
	using NTT::mul;
	namespace INV{
		int A[N], B[N], T[N], Al[N];
		inline void __inv(const poly &f, int lim)
		{
			A[0]=inv(f[0]);
			for(int l=1, n=2; l<=lim; ++l, n<<=1)
			{
				int t=n>>1;
				int len=1<<l;
				
				init(l);
				memcpy(B, (int*)&f[0], sizeof(int)*std::min(n, (int)f.size()));
				memcpy(T, A, sizeof(int)*n);
				std::fill(B+std::min(n, (int)f.size()), B+len, 0);
				
				ntt(A, len, 0), ntt(B, len, 0);
//				printf("len %d\n", len);
				if(l==lim) memcpy(Al, A, sizeof(int)*len);
				for(int i=0; i<len; ++i) B[i]=1ll*A[i]*B[i]%MOD;
				ntt(B, len, 1);
				std::fill(B, B+t, 0);
				ntt(B, len, 0);
				for(int i=0; i<len; ++i) A[i]=1ll*A[i]*B[i]%MOD;
				ntt(A, len, 1);
				std::fill(A, A+t, 0);
				for(int i=0; i<n; ++i) A[i]=mval(MOD+T[i]-A[i]);
			}
		}
		inline void Inv(const poly &a, poly &b, int n)
		{
			std::fill(A, A+(1<<glim(n-1)), 0);
			__inv(a, glim(n-1));
			b.resize(n);
			memcpy((int*)&b[0], A, sizeof(int)*n);
		}
		inline poly Inv(const poly &a, int n)
		{
			poly ret(n);
			Inv(a, ret, n);
			return ret;
		}
		
		int X[N], Y[N], Z[N], D[N];
		poly g;
		int Ar[N], Bl[N], Br[N], rs[N];
		inline void proc(const int *A, const int *B, int *C, bool oal, bool oar, bool obl, bool obr, int n)
		{
			n/=2;
			init(glim(2*n-1));
			if(!oal) memcpy(Al, A, sizeof(int)*n), std::fill(Al+n, Al+2*n, 0), ntt(Al, 2*n, 0);
			if(!oar) memcpy(Ar, A+n, sizeof(int)*n), std::fill(Ar+n, Ar+2*n, 0), ntt(Ar, 2*n, 0);
			if(!obl) memcpy(Bl, B, sizeof(int)*n), std::fill(Bl+n, Bl+2*n, 0), ntt(Bl, 2*n, 0);
			if(!obr) memcpy(Br, B+n, sizeof(int)*n), std::fill(Br+n, Br+2*n, 0), ntt(Br, 2*n, 0);
			for(int i=0; i<2*n; ++i) C[i]=1ll*Al[i]*Bl[i]%MOD, rs[i]=(1ll*Bl[i]*Ar[i]+1ll*Br[i]*Al[i])%MOD;
			ntt(C, 2*n, 1);
			ntt(rs, 2*n, 1);
			for(int i=0; i<n; ++i) inc(C[i+n], rs[i]);
		}
		inline void _dv(const poly &a, const poly &b, int n)
		{
			g.resize(n);
			n=1<<glim(n-1);
			n/=2;
			Inv(b, g, n);
			proc(g.data(), a.data(), Z, 1, 0, 0, 0, n);
			init(glim(2*n-1));
			std::fill(Z+n, Z+2*n, 0);//Q0
			memcpy(D, Z, sizeof(int)*(2*n));
			memcpy(Y, b.data(), sizeof(int)*std::min(2*n, (int)b.size()));
			std::fill(Y+std::min(2*n, (int)b.size()), Y+2*n, 0);
			ntt(D, 2*n, 0);//F(Q0)
			ntt(Y, 2*n, 0);
			for(int i=0; i<2*n; ++i) Y[i]=1ll*Y[i]*D[i]%MOD;
			ntt(Y, 2*n, 1);
			std::fill(Y, Y+n, 0);
			for(int i=n; i<2*n; ++i) if(i<a.size()) dec(Y[i], a[i]);
			proc(g.data(), Y+n, X, 1, 1, 0, 0, n);
			for(int i=0; i<n; ++i) X[i+n]=X[i], X[i]=0;
			std::fill(X, X+n, 0);
			for(int i=0; i<2*n; ++i) X[i]=mval(Z[i]+MOD-X[i]);
		}
		inline poly dv(const poly &a, const poly &b, int n)
		{
			poly ret(n);
			if(n<=2) { ret=mul(a, Inv(b, n)); ret.resize(n); return ret; }
			_dv(a, b, n);
			memcpy(ret.data(), X, sizeof(int)*n);
			return ret;
		}
	}
	using INV::Inv;
	using INV::dv;
	namespace DIV
	{
		poly D;
		inline void div(poly &a, poly &b, poly &q, poly &r)
		{
			int n=a.size()-1, m=b.size()-1;
			if(n<m)
			{
				r=a;
				return;
			}
			std::reverse(a.begin(), a.end());
			std::reverse(b.begin(), b.end());
			q=dv(a, b, n-m+1);
			q.resize(n-m+1);
			r=mul(q, b);
			r.resize(n+1);
			for(int i=0; i<=n; ++i) r[i]=mval(MOD+a[i]-r[i]);
			std::reverse(r.begin(), r.end());
			q.resize(n-m+1);
			std::reverse(q.begin(), q.end());
			std::reverse(a.begin(), a.end());
			std::reverse(b.begin(), b.end());
			r.resize(m);
		}
		inline vector<int> mod(poly &a, poly &b)
		{
			vector<int> ret;
			ret.resize(b.size()-1);
			div(a, b, D, ret);
			return ret;
		}
	}
	using DIV::div;
	using DIV::mod;
//	namespace LN{
//		poly A;
//		inline void ln(const poly &f, poly &g, int n)
//		{
//			A.resize(n);
//			for(int i=1; i<n; ++i) A[i-1]=i<f.size()?1ll*i*f[i]%MOD:0;
//			A=dv(A, f, n);
//			g.resize(n);
//			for(int i=n-1; i; --i) g[i]=1ll*inv(i)*A[i-1]%MOD;
//			g[0]=0;
//		}
//		inline poly ln(const poly &f, int n)
//		{
//			poly ret;
//			ln(f, ret, n);
//			return ret;
//		}
//	}
//	using LN::ln;
	namespace SemiConvol{
		const int Blim=4, B=1<<Blim, Thre=128;
		int f[N], G[N], rn;
		poly H[10][B];
		int exp_init(int x, int i) { return 1ll*x*i%MOD; }
		int exp_proc(int x, int i) { return 1ll*x*iv[i]%MOD; }
		void exp_final(int n)
		{
		}
		int ln_init(int x, int i) { return x; }
		int ln_proc(int x, int i)
		{
			return (MOD+1ll*i*G[i]-x)%MOD;
		}
		void ln_final(int n)
		{
			for(int i=0; i<n; ++i) f[i]=1ll*iv[i]*f[i]%MOD;
		}
		int inv_init(int x, int i) { return x; }
		int inv_proc(int x, int i)
		{
			return 1ll*(MOD-x)*f[0]%MOD;
		}
		void inv_final(int n)
		{
		}
		void Convol_init(const poly &g, int lim, int (*initp)(int, int), int st)
		{
			ext(1<<lim);
			std::fill(f, f+(1<<lim), 0);
			std::fill(G, G+(1<<lim), 0);
			f[0]=st;
			G[0]=0;
			memcpy(G, g.data(), sizeof(int)*std::min((int)g.size(), (1ull<<lim)));
			for(int i=0; i<(1<<lim); ++i) G[i]=initp(G[i], i);//1ll*G[i]*i%MOD;
//			for(int i=0; i<(1<<lim); ++i) printf("%d ", G[i]);
//			puts("");
			for(int i=lim; i>=Blim; i-=Blim)
			{
				if((1<<i)<=Thre) break;
				int len=1<<(i-Blim);
				init(i-Blim+1);
				int id=i/Blim;
				for(int j=0; j<B-1; ++j)
				{
					if(j*len>=rn) break;
					H[id][j].resize(len*2);
					memcpy(H[id][j].data(), G+j*len, sizeof(int)*(2*len));
					ntt(H[id][j].data(), 2*len, 0);
				}
			}
		}
		void solve(int lim, int l, int r, int (*proc)(int, int))
		{
			if(l>=rn) return;
			if(r-l<=Thre)
			{
				for(int i=l; i<r; ++i)
				{
					if(i!=0) f[i]=proc(f[i], i);
//					printf("fa %d %d\n", i, f[i]);
					for(int j=i+1; j<r; ++j) f[j]=(f[j]+1ll*f[i]*G[j-i])%MOD;
				}
				return;
			}
			int len=1<<(lim-Blim), id=lim/Blim, L=(std::min(r, rn)-l+len-1)/len;
			poly cur[B];
			for(int i=0; i<L; ++i) cur[i].resize(len*2);
			for(int i=0; i<L; ++i)
			{
				if(i!=0)
				{
					init(lim-Blim+1);
					ntt(cur[i].data(), 2*len, 1);
					for(int j=0; j<len; ++j) inc(f[j+len*i+l], cur[i][j+len]);
				}
				solve(lim-Blim, l+i*len, l+i*len+len, proc);
				if(i!=L-1)
				{
					memcpy(cur[i].data(), f+l+i*len, sizeof(int)*len);
					std::fill(cur[i].data()+len, cur[i].data()+2*len, 0);
					init(lim-Blim+1);
					ntt(cur[i].data(), 2*len, 0);
					for(int j=i+1; j<L; ++j)
					{
						for(int k=0; k<2*len; ++k)
							cur[j][k]=(cur[j][k]+1ll*cur[i][k]*H[id][j-i-1][k])%MOD;
					}
				}
			}
		}
		inline void conv(const poly &F, poly &g, int n, int (*init) (int, int), int (*proc) (int, int), void(*final)(int), int st)
		{
			int lim=glim(n-1);
			rn=n;
			Convol_init(F, lim, init, st);
			solve(lim, 0, 1<<lim, proc);
			final(n);
			g.resize(n);
			memcpy(g.data(), f, sizeof(int)*n);
		}
		inline poly conv(const poly &a, int n, int (*init) (int, int), int (*proc) (int, int), void (*final)(int), int st)
		{
			poly ret;
			conv(a, ret, n, init, proc, final, st);
			return ret;
		}
		poly exp(const poly &a, int n)
		{
			return conv(a, n, exp_init, exp_proc, exp_final, 1);
		}
		poly ln(const poly &a, int n)
		{
			return conv(a, n, ln_init, ln_proc, ln_final, 0);
		}
		poly Inv(const poly &a, int n)
		{
			return conv(a, n, inv_init, inv_proc, inv_final, qpow(a[0], MOD-2));
		}
	}
	using SemiConvol::exp_init;
	using SemiConvol::exp_proc;
	using SemiConvol::exp_final;
	using SemiConvol::ln_init;
	using SemiConvol::ln_proc;
	using SemiConvol::ln_final;
	using SemiConvol::conv;
	using SemiConvol::exp;
	using SemiConvol::ln;
	using SemiConvol::Inv;
	/*
	namespace EXP2{
		const int Blim=4, B=1<<Blim, Thre=128;
		int f[N], G[N], rn;
		poly H[10][B];
		void exp_init(const poly &g, int lim)
		{
			ext(1<<lim);
			std::fill(f, f+(1<<lim), 0);
			std::fill(G, G+(1<<lim), 0);
			memcpy(G, g.data(), sizeof(int)*std::min((int)g.size(), (1ull<<lim)));
			for(int i=0; i<=(1<<lim); ++i) G[i]=1ll*G[i]*i%MOD;
			for(int i=lim; i>=Blim; i-=Blim)
			{
				if((1<<i)<=Thre) break;
				int len=1<<(i-Blim);
				init(i-Blim+1);
				int id=i/Blim;
				for(int j=0; j<B-1; ++j)
				{
					if(j*len>=rn) break;
					H[id][j].resize(len*2);
					memcpy(H[id][j].data(), G+j*len, sizeof(int)*(2*len));
					ntt(H[id][j].data(), 2*len, 0);
				}
			}
		}
		void exp(int lim, int l, int r)
		{
			if(l>=rn) return;
			if(r-l<=Thre)
			{
				for(int i=l; i<r; ++i)
				{
					if(i==0) f[i]=1;
					else f[i]=1ll*iv[i]*f[i]%MOD;
					for(int j=i+1; j<r; ++j) f[j]=(f[j]+1ll*f[i]*G[j-i])%MOD;
				}
				return;
			}
			int len=1<<(lim-Blim), id=lim/Blim, L=(std::min(r, rn)-l+len-1)/len;
			poly cur[B];
			for(int i=0; i<L; ++i) cur[i].resize(len*2);
			for(int i=0; i<L; ++i)
			{
				if(i!=0)
				{
					init(lim-Blim+1);
					ntt(cur[i].data(), 2*len, 1);
					for(int j=0; j<len; ++j) inc(f[j+len*i+l], cur[i][j+len]);
				}
				exp(lim-Blim, l+i*len, l+i*len+len);
				if(i!=L-1)
				{
					memcpy(cur[i].data(), f+l+i*len, sizeof(int)*len);
					std::fill(cur[i].data()+len, cur[i].data()+2*len, 0);
					init(lim-Blim+1);
					ntt(cur[i].data(), 2*len, 0);
					for(int j=i+1; j<L; ++j)
					{
						for(int k=0; k<2*len; ++k)
							cur[j][k]=(cur[j][k]+1ll*cur[i][k]*H[id][j-i-1][k])%MOD;
					}
				}
			}
		}
		inline void exp(const poly &F, poly &g, int n)
		{
			int lim=glim(n-1);
			rn=n;
			exp_init(F, lim);
			exp(lim, 0, 1<<lim);
			g.resize(n);
			memcpy(g.data(), f, sizeof(int)*n);
		}
		inline poly exp(const poly &a, int n)
		{
			poly ret;
			exp(a, ret, n);
			return ret;
		}
	}
	using EXP2::exp;
	*/
	/*
	namespace EXP{
		int G[N], H[N], FG[N], A[N], B[N], C[N];
		poly f1;
		
		inline void _exp(const poly &f, int lim)
		{
			G[0]=H[0]=1;
			FG[0]=FG[1]=G[0];
			f1=deri(f);
			ext(1<<lim);
			f1.resize((1<<lim)+1);
//			print(f1);
			for(int l=1, n=1; l<=lim; ++l, n<<=1)
			{
				memcpy(A, f1.data(), sizeof(int)*(n-1));
				A[n-1]=0;
				init(l-1);
				ntt(A, n, 0);
				for(int i=0; i<n; ++i) A[i]=1ll*A[i]*FG[i]%MOD;
				ntt(A, n, 1);
				G[n]=0;
				for(int i=0; i<n; ++i) A[i]=(MOD+1ll*(i+1)*G[i+1]-A[i])%MOD;
				for(int i=0; i<n-1; ++i) A[i+n]=A[i], A[i]=0;
				//g0'-g0f0'
				
				memcpy(C, G, sizeof(int)*n);
				std::fill(C+n, C+2*n, 0);
				int ml=qpow(NTT::g, (MOD-1)/(2*n));
				for(int i=0, cur=1; i<n; ++i, cur=1ll*cur*ml%MOD) C[i]=1ll*C[i]*cur%MOD;
//				init(l-1);
				ntt(C, n, 0);
//				init(l);
				for(int i=2*n-1; ~i; --i)
				{
					FG[i]=(i&1)?C[i>>1]:FG[i>>1];
				}
//				for(int i=0; i<n; ++i) F2G[2*i]=FG[i];
//				for(int i=0; i<n; ++i) F2G[2*i+1]=C[i];
				//F2G
				
				memcpy(B, H, sizeof(int)*n);
				std::fill(B+n, B+2*n, 0);
				init(l);
				ntt(B, 2*n, 0);//FH0
				ntt(A, 2*n, 0);
				for(int i=0; i<2*n; ++i) A[i]=1ll*A[i]*B[i]%MOD;
				ntt(A, 2*n, 1);
				std::fill(A, A+n-1, 0);
				//h0(g0'-g0f0')
				
				for(int i=0; i<n-1; ++i) inc(A[i], f1[i]);
				for(int i=2*n-1; i>=n; --i) A[i]=1ll*A[i-1]*iv[i]%MOD;
				for(int i=0; i<2*n; ++i) dec(A[i], f[i]);
				//integ(h0(g0'-g0f0')+f0')-f
				std::fill(A, A+n, 0);
				
				ntt(A, 2*n, 0);
				for(int i=0; i<2*n; ++i) A[i]=1ll*A[i]*FG[i]%MOD;
				ntt(A, 2*n, 1);
				for(int i=n; i<2*n; ++i) G[i]=mval(MOD-A[i]);
				//G
				
				if(l==lim) break;
				memcpy(FG, G, sizeof(int)*(2*n));
				ntt(FG, 2*n, 0);
				for(int i=0; i<2*n; ++i) C[i]=1ll*FG[i]*B[i]%MOD;
				ntt(C, 2*n, 1);
				std::fill(C, C+n, 0);
				ntt(C, 2*n, 0);
				for(int i=0; i<2*n; ++i) C[i]=1ll*B[i]*C[i]%MOD;
				ntt(C, 2*n, 1);
				for(int i=n; i<2*n; ++i) H[i]=mval(MOD-C[i]);
				//FG B
			}
		}
		inline void exp(const poly &f, poly &g, int n)
		{
			g=f;
			g.resize(1<<glim(n-1));
			_exp(g, glim(n-1));
			g=to_poly(G, n);
		}
		inline poly exp(const poly &a, int n)
		{
			poly ret(n);
			exp(a, ret, n);
			return ret;
		}
	}
	using EXP::exp;
	*/
	namespace Cipolla{
		inline int myrd(void) { return rand(); }
		int mul;
		struct comp{
			int x, y;
			comp operator *(const comp &a) const
			{
				return comp{(1ll*x*a.x+1ll*y*a.y%MOD*mul)%MOD, (1ll*y*a.x+1ll*x*a.y)%MOD};
			}
		};
		inline comp my_qpow(comp x, int p)
		{
			comp ret=comp{1, 0};
			while(p)
			{
				if(p&1) ret=ret*x;
				p>>=1, x=x*x;
			}
			return ret;
		}
		inline int cipolla(int x)
		{
			if(qpow(x, (MOD-1)/2)==MOD-1) return -1;
			int a=0;
			while(1)
			{
				a=myrd()%MOD;
				if(qpow((MOD+1ll*a*a-x)%MOD, (MOD-1)/2)==MOD-1) break;
			}
			mul=(MOD+1ll*a*a-x)%MOD;
			int t=my_qpow(comp{a, 1}, (MOD+1)/2).x;
			return std::min(MOD-t, t);
		}
	}
	using Cipolla::cipolla;
	namespace SQRT{
		int G[N], H[N], FG[N], A[N], B[N], C[N];
		void _sqrt(const poly &f, int lim)
		{
			int iv2=qpow(2, MOD-2);
			G[0]=cipolla(f[0]), H[0]=qpow(G[0], MOD-2);
			FG[0]=FG[1]=G[0];
			for(int l=1, n=1; l<=lim; ++l, n<<=1)
			{
				for(int i=0; i<n; ++i) B[i]=1ll*FG[i]*FG[i]%MOD;
				init(l-1);
				ntt(B, n, 1);
				for(int i=0; i<n; ++i) B[i+n]=mval(MOD+B[i]-f[i]), B[i]=0;
				for(int i=n; i<2*n; ++i) dec(B[i], f[i]);
				memcpy(A, H, sizeof(int)*n);
				std::fill(A+n, A+2*n, 0);
				init(l);
				ntt(B, 2*n, 0);
				ntt(A, 2*n, 0);
				for(int i=0; i<2*n; ++i) C[i]=1ll*B[i]*A[i]%MOD;
				ntt(C, 2*n, 1);
				std::fill(C, C+n, 0);
				for(int i=n; i<=2*n; ++i) G[i]=mval(MOD-1ll*C[i]*iv2%MOD);
				memcpy(FG, G, sizeof(int)*(2*n));
				if(l==lim) break;
				ntt(FG, 2*n, 0);
				for(int i=0; i<2*n; ++i) C[i]=1ll*A[i]*FG[i]%MOD;
				ntt(C, 2*n, 1);
				std::fill(C, C+n, 0);
				ntt(C, 2*n, 0);
				for(int i=0; i<2*n; ++i) C[i]=1ll*A[i]*C[i]%MOD;
				ntt(C, 2*n, 1);
				std::fill(C, C+n, 0);
				for(int i=n; i<2*n; ++i) dec(H[i], C[i]);
			}
		}
		inline poly Sqrt(const poly &a, int n)
		{
			poly f=a;
			f.resize(1<<glim(n-1));
			_sqrt(f, glim(n-1));
			return to_poly(G, n);
		}
	}
	using SQRT::Sqrt;
	namespace POWER{
		inline poly Power(poly f, int k, int k1)
		{
			int n=f.size();
			int t=0;
			while(!f[t]) ++t;
			if(1ll*t*k>=n) { std::fill(f.begin(), f.end(), 0); return f; }
			int ml=qpow(f[t], k1), iv=inv(f[t]);
			for(int i=t; i<n; ++i) f[i]=1ll*f[i]*iv%MOD;
			f=slice(f, t, f.size());
			f=ln(f, n-t*k);
			for(int i=0; i<n-t*k; ++i) f[i]=1ll*k*f[i]%MOD;
			f=exp(f, n-t*k);
			poly ret(n);
			for(int i=0; i<n; ++i) ret[i]=(t&&t*k>i)?0:1ll*f[i-t*k]*ml%MOD;
			return ret;
		}
	}
	using POWER::Power;
	namespace GVAL{
		#define lid (id<<1)
		#define rid (id<<1|1)
		int ans[N], pos[N];
		vector<int> g[N];
		inline void build(int id, int l, int r)
		{
			g[id].resize(r-l+2);
			if(l==r) { g[id][0]=MOD-pos[l], g[id][1]=1; return; }
			int mid=(l+r)>>1;
			build(lid, l, mid), build(rid, mid+1, r);
			mul(g[lid], g[rid], g[id], g[lid].size()-1, g[rid].size()-1);
		}
		inline void solve(int id, int l, int r, vector<int> f)
		{
			if(l==r) { ans[l]=f[0]; return; }
			int mid=(l+r)>>1;
			solve(lid, l, mid, mod(f, g[lid]));
			solve(rid, mid+1, r, mod(f, g[rid]));
		}
		template <class _T, class _T1, class _T2> inline void gval(_T f, int n, _T1 p, int m, _T2 &ret)
		{
			memcpy(pos, (int*)&p[0], sizeof(int)*(m+1));
			build(1, 1, m);
			solve(1, 1, m, mod(f, g[1]));
			memcpy((int*)&ret[0], ans, sizeof(int)*(m+1));
		}
	}
	using GVAL::gval;
	namespace Lagrange{
		#define lid (id<<1)
		#define rid (id<<1|1)
		int x[N], y[N], val[N];
		poly g[N], h[N];
		void build(int id, int l, int r)
		{
			if(l==r) { g[id].resize(2); g[id][1]=1, g[id][0]=MOD-x[l]; return; }
			int mid=(l+r)>>1;
			build(lid, l, mid), build(rid, mid+1, r);
			g[id]=mul(g[lid], g[rid]);
		}
		void solve(int id, int l, int r)
		{
			if(l==r) { h[id].resize(1); h[id][0]=1ll*y[l]*inv(val[l])%MOD; return; }
			int mid=(l+r)>>1;
			solve(lid, l, mid), solve(rid, mid+1, r);
			h[id]=add(mul(g[lid], h[rid]), mul(g[rid], h[lid]));
		}
		template <class _T> inline poly Lag(const _T &a, const _T &b, int n)
		{
			memcpy(x, (int*)&a[0], sizeof(int)*(n+1));
			memcpy(y, (int*)&b[0], sizeof(int)*(n+1));
			build(1, 1, n);
			gval(deri(g[1]), n, a, n, val);
			solve(1, 1, n);
			return h[1];
		}
	}
	using Lagrange::Lag;
	namespace Transform{
		poly g;
		inline poly add_var(poly f, int x)
		{
			if(f.size()>=tp) ext(f.size());
			int n=f.size()-1;
			g.resize(n+1);
			g[0]=1;
			for(int i=1; i<=n; ++i) g[i]=1ll*g[i-1]*iv[i]%MOD*x%MOD;
			for(int i=0; i<=n; ++i) f[i]=1ll*fac[i]*f[i]%MOD;
			std::reverse(g.begin(), g.end());
			f=mul(f, g);
			f=slice(f, n, 2*n+1);
			for(int i=0; i<=n; ++i) f[i]=1ll*f[i]*iiv[i]%MOD;
			return f;
		}
		inline poly mul_var(poly f, int x)
		{
			for(int i=0, cur=1; i<f.size(); ++i, cur=1ll*cur*x%MOD) f[i]=1ll*f[i]*cur%MOD;
			return f;
		}
	}
	using Transform::add_var;
	using Transform::mul_var;
	namespace Arbitrary_Basis{
		struct Lpow{
			#define B 40000
			int pw1[B+5], pw2[B+5];
			void init(int x)
			{
				pw1[0]=1;
				for(int i=1; i<=B; ++i) pw1[i]=1ll*pw1[i-1]*x%MOD;
				pw2[0]=1;
				int c=qpow(x, B);
				for(int i=1; i<=B; ++i) pw2[i]=1ll*pw2[i-1]*c%MOD;
			}
			inline int lp(int p) { return 1ll*pw1[p%B]*pw2[p/B]%MOD; }
			#undef B
		}lp;
		poly g;
		template <class _T> inline void ABDFT(poly f, _T &ans, int w, int m)
		{
			lp.init(w);
			int n=f.size()-1;
			g.resize(n+m+1);
			for(int i=0; i<=n+m; ++i) g[i]=lp.lp(1ll*i*(i-1)/2%(MOD-1));
			for(int i=0; i<=n; ++i) f[i]=1ll*f[i]*lp.lp(MOD-1-1ll*i*(i-1)/2%(MOD-1))%MOD;
			std::reverse(f.begin(), f.end());
			f=mul(f, g);
			f=slice(f, n, n+m+1);
			for(int i=0; i<=m; ++i) f[i]=1ll*f[i]*lp.lp(MOD-1-1ll*i*(i-1)/2%(MOD-1))%MOD;
			memcpy((int*)&ans[0], (int*)&f[0], sizeof(int)*(m+1));
		}
	}
	using Arbitrary_Basis::ABDFT;
}
using namespace Poly;
poly a, b;
signed main()
{
	init();
    a.resize(3), b.resize(3);
    a[0]=b[0]=1;
    a=ln(a, 3), b=ln(b, 3);
    a=add(a, b);
    a=exp(a, 3);
    printf("%llu\n", a[1]);
    return 0;
}

这发代码交上去只有20分，实在是不知道为啥，跪求大佬帮忙调试。