#include using namespace std; //入力が必ず-mod<=a //mod<2^30. struct modint{ //mod変更が不可能. public: long long v; static void setmod(int m){} //飾り. static constexpr long long getmod(){return mod;} modint():v(0){} template modint(T a):v(a){if(v < 0) v += mod;} long long val()const{return v;} modint &operator=(const modint &b) = default; modint &operator+()const{return (*this);} modint operator-()const{return modint(0)-(*this);} modint operator+(const modint b)const{return modint(v)+=b;} modint operator-(const modint b)const{return modint(v)-=b;} modint operator*(const modint b)const{return modint(v)*=b;} modint operator/(const modint b)const{return modint(v)/=b;} modint &operator+=(const modint b){ v += b.v; if(v >= mod) v -= mod; return *this; } modint &operator-=(const modint b){ v -= b.v; if(v < 0) v += mod; return *this; } modint &operator*=(const modint b){v = v*b.v%mod; return *this;} modint &operator/=(modint b){ //b!=0 mod素数が必須. assert(b.v != 0); (*this) *= b.pow(mod-2); return *this; } modint pow(long long n)const{ modint ret = 1,p = v; if(n < 0) p = p.inv(),n = -n; while(n){ if(n&1) ret *= p; p *= p; n >>= 1; } return ret; } modint inv()const{return pow(mod-2);} //素数mod必須. modint &operator++(){*this += 1; return *this;} modint &operator--(){*this -= 1; return *this;} modint operator++(int){modint ret = *this; *this += 1; return ret;} modint operator--(int){modint ret = *this; *this -= 1; return ret;} friend bool operator==(const modint a,const modint b){return a.v==b.v;} friend bool operator!=(const modint a,const modint b){return a.v!=b.v;} friend bool operator<(const modint a,const modint b){return a.v=(const modint a,const modint b){return a.v>=b.v;} friend bool operator>(const modint a,const modint b){return a.v>b.v;} friend ostream &operator<<(ostream &os,const modint a){return os<>(istream &is,modint &a){ //入力はmodをとってくれる. long long x; is >> x; x %= mod; a = modint(x); return is; } }; using mint = modint<998244353>; const long long mod = 998244353; namespace to_fold{ __int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;} pair invgcd(long long a,long long b){ //return {gcd(a,b),x} (xa≡g(mod b)) a = safemod(a,b); if(a == 0) return {b,0}; long long x = 0,y = 1,memob = b; while(a){ long long q = b/a; b -= a*q; swap(x,y); y -= q*x; swap(a,b); } if(x < 0) x += memob/b; return {b,x}; } template long long Garner(const vector &A,const vector &M){ __int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須. for(int i=1; i struct fftinfo{ static bool First; static mint g,sum_e[30],sum_ie[30]; //sum_e[i]=Π[j=0~i-1]ies[j] * es[i],sum_ie[i]=Π[i=0~j-1]es[j] * ies[i]. static mint divpow2[30]; //div[i] = 1/(2^i). static mint Zeta[30]; fftinfo(){ if(!First) return; First = false; const long long mod = mint::getmod(); if(mod == 998244353) g = 3; else if(mod == 754974721) g = 11; else if(mod == 167772161) g = 3; else if(mod == 469762049) g = 3; else assert(false); //現状RE. mint es[30],ies[30]; //es[i]^(2^(2+i))=1. int cnt2 = countzero(mod-1); mint e = g.pow((mod-1)>>cnt2),ie = e.inv(); for(int i=cnt2; i>=2; i--){ //e^(2^i)=1; es[i-2] = e,e *= e; ies[i-2] = ie,ie *= ie; } mint rot = 1; for(int i=0; i<=cnt2-2; i++) sum_e[i] = es[i]*rot,rot *= ies[i]; rot = 1; for(int i=0; i<=cnt2-2; i++) sum_ie[i] = ies[i]*rot,rot *= es[i]; mint div2n = 1,div2 = mint(1)/2; for(int i=0; i<30; i++) divpow2[i] = div2n,div2n *= div2; for(int i=0; i<=cnt2; i++) Zeta[i] = g.pow((mod-1)/(2< bool fftinfo::First=true; template mint fftinfo::g; template mint fftinfo::sum_e[30]; template mint fftinfo::sum_ie[30]; template mint fftinfo::divpow2[30]; template mint fftinfo::Zeta[30]; template void NTT(vector &A){ //ACLを超参考にしてる. int n = A.size(); assert((n&-n) == n); fftinfo info; int h = countzero(n); for(int ph=1; ph<=h; ph++){ int w = 1<<(ph-1),p = 1<<(h-ph); mint rot = 1; for(int s=0; s void INTT(vector &A){ int n = A.size(); assert((n&-n) == n); fftinfo info; const unsigned int mod = mint::getmod(); int h = countzero(n); for(int ph=h; ph>0; ph--){ int w = 1<<(ph-1),p = 1<<(h-ph); mint irot = 1; for(int s=0; s vector convolution(vector A,vector B){ //mintじゃないのを突っ込まないように!!!. int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1; if(siza == 0 || sizb == 0) return {}; if(min(siza,sizb) <= 60){ //naive. vector ret(sizc); if(siza >= sizb){for(int i=0; i vector convolution_ll(const vector &A,const vector &B){ //long longに収まる範囲. int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; vector ret(sizc); if(min(siza,sizb) <= 200){ //naive 200はやばい?. if(siza >= sizb){for(int i=0; i; using mint2 = modint; using mint3 = modint; vector a1(siza),b1(sizb); vector a2(siza),b2(sizb); vector a3(siza),b3(sizb); for(int i=0; i C1 = convolution(a1,b1); for(int i=0; i C2 = convolution(a2,b2); for(int i=0; i C3 = convolution(a3,b3); vector offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3}; for(int i=0; i vector convolution_llmod(const vector &A,const vector &B){ int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; vector ret(sizc); if(min(siza,sizb) <= 200){ for(int i=0; i; using mint2 = modint; using mint3 = modint; vector a1(siza),b1(sizb); vector a2(siza),b2(sizb); vector a3(siza),b3(sizb); for(int i=0; i C1 = convolution(a1,b1); for(int i=0; i C2 = convolution(a2,b2); for(int i=0; i C3 = convolution(a3,b3); for(int i=0; i A = {C1.at(i).v,C2.at(i).v,C3.at(i).v}; vector M = {mod1,mod2,mod3}; ret.at(i) = Garner(A,M); } return ret; } template vector<__int128_t> convolution_i128(const vector &A,const vector &B){ //10^25に収まる範囲. int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1; if(siza == 0 || sizb == 0) return {}; vector<__int128_t> ret(sizc); if(min(siza,sizb) <= 200){ //naive 200はやばい?. if(siza >= sizb){for(int i=0; i; using mint2 = modint; using mint3 = modint; vector a1(siza),b1(sizb); vector a2(siza),b2(sizb); vector a3(siza),b3(sizb); for(int i=0; i C1 = convolution(a1,b1); for(int i=0; i C2 = convolution(a2,b2); for(int i=0; i C3 = convolution(a3,b3); for(int i=0; i convolution_int(const vector &A,const vector &B){ //intに収まる範囲. if(A.size() == 0 || B.size() == 0) return {}; vector ret; if(min(A.size(),B.size()) <= 60){ ret.resize(A.size()+B.size()-1); for(int i=0; i; vector X(A.size()),Y(B.size()),Z; for(int i=0; i void NTTdoubling(vector &A){ //NTTの原理を忘れているため何やってるのか意味が分からない NTT-friendly専用. //INTT->resize(2倍)->NTTの代わりにcopy->INTT->謎の操作->NTT->push sizeが小さい時は効率悪いらしいよ. int n = A.size(); fftinfo info; vector B = A; INTT(B); mint rot = 1,zeta = info.Zeta[countzero(n)]; for(auto &v : B) v *= rot,rot *= zeta; NTT(B); A.reserve(n<<1); for(auto &v : B) A.push_back(v); } bool isNTTfriendly(long long mod){ if(mod == 998244353 || mod == 754974721 || mod == 16777216 || mod == 469762049) return true; return false; //現状false 原子根求める機能を追加してから. int have2 = countzero(mod-1); return have2 >= 20;//とりあえず2^20でokとする; } } using namespace to_fold; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin >> N >> M; int n2 = 1<必要なサイズ fac->x! facinv->1/x! inv->1/x. vector fac(Limit+1,1),facinv(Limit+1); { int mod = mint::getmod(),invstart = min(mod-1,Limit); for(int i=1; i<=Limit; i++) fac.at(i) = fac.at(i-1)*i; facinv.at(invstart) = fac.at(invstart).inv(); for(int i=invstart-1; i>=0; i--) facinv.at(i) = facinv.at(i+1)*(i+1); } //vector inv(Limit+1); for(int i=1; i<=Limit; i++) inv.at(i) = fac.at(i-1)*facinv.at(i); //必要なら解放. auto nCr = [&](int n,int r) -> mint { if(n < r || r < 0 || n < 0) return 0; return fac.at(n)*facinv.at(r)*facinv.at(n-r); }; vector X(2),Y(2); X.at(0) = 1,Y.at(1) = 1; int len = 1; mint div2 = mint(1)/2; for(int d=0; d nX,nY,nZ; nX = convolution(X,X); nZ = convolution(X,Y); nY = convolution(Y,Y); for(int i=0; i