#ifdef t9unkubj #include"template.h" //#include"template_no_debug.h" #else #undef _GLIBCXX_DEBUG #pragma GCC optimize("O3") #define dbg(...) 199958 using namespace std; #include using uint=unsigned; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; templateusing vc=vector; templateusing vvc=vc>; templateusing vvvc=vvc>; using vi=vc; using vvi=vc; using vvvi=vc; using vl=vc; using vvl=vc; using vvvl=vc; templateusing smpq=priority_queue,greater>; templateusing bipq=priority_queue; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define mp make_pair #define pb push_back #define eb emplace_back #define fi first #define se second #define is insert #define bg begin() #define ed end() void scan(int&a) { cin >> a; } void scan(ll&a) { cin >> a; } void scan(string&a) { cin >> a; } void scan(char&a) { cin >> a; } void scan(uint&a) { cin >> a; } void scan(ull&a) { cin >> a; } void scan(bool&a) { cin >> a; } void scan(ld&a){ cin>> a;} template void scan(vector&a) { for(auto&x:a) scan(x); } void read() {} template void read(Head&head, Tail&... tail) { scan(head); read(tail...); } #define INT(...) int __VA_ARGS__; read(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__); #define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__); #define STR(...) string __VA_ARGS__; read(__VA_ARGS__); #define CHR(...) char __VA_ARGS__; read(__VA_ARGS__); #define DBL(...) double __VA_ARGS__; read(__VA_ARGS__); #define LD(...) ld __VA_ARGS__; read(__VA_ARGS__); #define VC(type, name, ...) vector name(__VA_ARGS__); read(name); #define VVC(type, name, size, ...) vector> name(size, vector(__VA_ARGS__)); read(name); void print(int a) { cout << a; } void print(ll a) { cout << a; } void print(string a) { cout << a; } void print(char a) { cout << a; } void print(uint a) { cout << a; } void print(bool a) { cout << a; } void print(ull a) { cout << a; } void print(double a) { cout << a; } void print(ld a){ cout<< a; } template void print(vectora) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout< void PRT(T a) { print(a); cout < void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; } template bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template bool chmax(T &x, F y){ if(x int popcount(T n){ return __builtin_popcountll(n); } template T sum(vc&a){ return accumulate(all(a),T(0)); } template T max(vc&a){ return *max_element(all(a)); } template T min(vc&a){ return *min_element(all(a)); } template void unique(vc&a){ a.erase(unique(all(a)),a.end()); } vvi readgraph(int n,int m,int off = -1){ vvi g(n); rep(i, m){ int u,v; cin>>u>>v; u+=off,v+=off; g[u].push_back(v); g[v].push_back(u); } return g; } vvi readtree(int n,int off=-1){ return readgraph(n,n-1,off); } template vc presum(vc &a){ vc ret(a.size()+1); rep(i,a.size())ret[i+1]=ret[i]+a[i]; return ret; } template vc &operator+=(vc &a,F b){ for (auto&v:a)v += b; return a; } template vc &operator-=(vc&a,F b){ for (auto&v:a)v-=b; return a; } template vc &operator*=(vc&a,F b){ for (auto&v:a)v*=b; return a; } #endif double pass_time=0; #pragma once template F modpow(T x,G p,F m){ T ret=1%m; x%=m; while(p){ if(p&1)ret=(1ll*ret*x)%m; x=(1ll*x*x)%m; p>>=1; } return ret; } template T extgcd(T a,T b,T&x,T&y){//ax+by=gcd(a,b)となるようなもの if(b==0){ x=1; y=0; return a; }else{ T res=extgcd(b,a%b,y,x); y-=(a/b)*x; return res; } } template pair inv(T x,T m){ T a1,a2; T res=extgcd(x,m,a1,a2); return {a1,m/res}; } constexpr int mod=998244353; struct mint{ long long val; inline long long fast(long long x){ if(x=0)return x; x%=mod; if(x<0)x+=mod; return x; } mint():val(0){} mint(long long val):val(fast(val)){} mint power(long long m)const { mint res(1); mint ret(*this); while(m){ if(m&1)res*=ret; ret*=ret; m>>=1; } return res; } mint& operator++() { val++; if (val == mod) val = 0; return *this; } mint& operator--() { if (val == 0)val=mod; val--; return *this; } mint operator++(int) { mint result = *this; ++*this; return result; } mint operator--(int) { mint result = *this; --*this; return result; } mint operator-() const { return mint(-val); } friend mint operator +(const mint&a,const mint&b) noexcept{ return mint(a)+=b; } friend mint operator -(const mint&a,const mint&b) noexcept{ return mint(a)-=b; } friend mint operator *(const mint&a,const mint&b) noexcept{ return mint(a)*=b; } friend mint operator /(const mint&a,const mint&b) noexcept{ return mint(a)/=b; } mint& operator+=(const mint&a)noexcept{ val+=a.val; if(val>=mod)val-=mod; return *this; } mint& operator-=(const mint&a)noexcept{ val-=a.val; if(val<0)val+=mod; return *this; } mint& operator*=(const mint&a){ val*=a.val; val=fast(val); return *this; } mint& operator/=(const mint&a){ val*=inv(a.val,mod).first; val=fast(val); return *this; } bool operator == (const mint&x)const noexcept{ return this->val==x.val; } bool operator != (const mint&x)const noexcept{ return this->val!=x.val; } friend ostream& operator << (ostream &os, const mint &x) noexcept { return os << x.val; } friend istream& operator >> (istream &is, mint &x) noexcept { long long v; is >> v; x=mint(v); return is; } }; vectorfact(1,1),invfact(1,1); void build(int n){ if(n<(int)fact.size())return; fact=invfact=vector(n+1); fact[0]=1; for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i; invfact[n]=(1/fact[n]); for(int i=n-1;i>=0;i--)invfact[i]=invfact[i+1]*(i+1); } mint C(int a,int b){//aCb if(a<0||b<0||a-b<0)return mint(0); while((int)fact.size()<=a){ fact.push_back(fact.back()*(fact.size())); } while((int)invfact.size()<=a){ invfact.push_back(invfact.back()/invfact.size()); } return fact[a]*invfact[b]*invfact[a-b]; } mint P(int a,int b){ if(a pair mod_solve(T a,T b,T m){//ax=b mod mとなるxを返す a%=m,b%=m;if(a<0)a+=m;if(b<0)b+=m; T g=gcd(gcd(a,b),m); a/=g,b/=g,m/=g; if(gcd(a,m)>1)return {-1,-1}; return {(inv(a,m).first*b)%m,inv(a,m).second}; } namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } // @param m `1 <= m` // @return x mod m constexpr long long safe_mod(long long x, long long m) { x %= m; if (x < 0) x += m; return x; } // Fast modular multiplication by barrett reduction // Reference: https://en.wikipedia.org/wiki/Barrett_reduction // NOTE: reconsider after Ice Lake struct barrett { unsigned int _m; unsigned long long im; // @param m `1 <= m < 2^31` barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {} // @return m unsigned int umod() const { return _m; } // @param a `0 <= a < m` // @param b `0 <= b < m` // @return `a * b % m` unsigned int mul(unsigned int a, unsigned int b) const { // [1] m = 1 // a = b = im = 0, so okay // [2] m >= 2 // im = ceil(2^64 / m) // -> im * m = 2^64 + r (0 <= r < m) // let z = a*b = c*m + d (0 <= c, d < m) // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2 // ((ab * im) >> 64) == c or c + 1 unsigned long long z = a; z *= b; #ifdef _MSC_VER unsigned long long x; _umul128(z, im, &x); #else unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64); #endif unsigned int v = (unsigned int)(z - x * _m); if (_m <= v) v += _m; return v; } }; // @param n `0 <= n` // @param m `1 <= m` // @return `(x ** n) % m` constexpr long long pow_mod_constexpr(long long x, long long n, int m) { if (m == 1) return 0; unsigned int _m = (unsigned int)(m); unsigned long long r = 1; unsigned long long y = safe_mod(x, m); while (n) { if (n & 1) r = (r * y) % _m; y = (y * y) % _m; n >>= 1; } return r; } // Reference: // M. Forisek and J. Jancina, // Fast Primality Testing for Integers That Fit into a Machine Word // @param n `0 <= n` constexpr bool is_prime_constexpr(int n) { if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; long long d = n - 1; while (d % 2 == 0) d /= 2; constexpr long long bases[3] = {2, 7, 61}; for (long long a : bases) { long long t = d; long long y = pow_mod_constexpr(a, t, n); while (t != n - 1 && y != 1 && y != n - 1) { y = y * y % n; t <<= 1; } if (y != n - 1 && t % 2 == 0) { return false; } } return true; } template constexpr bool is_prime = is_prime_constexpr(n); // @param b `1 <= b` // @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g constexpr std::pair inv_gcd(long long a, long long b) { a = safe_mod(a, b); if (a == 0) return {b, 0}; // Contracts: // [1] s - m0 * a = 0 (mod b) // [2] t - m1 * a = 0 (mod b) // [3] s * |m1| + t * |m0| <= b long long s = b, t = a; long long m0 = 0, m1 = 1; while (t) { long long u = s / t; s -= t * u; m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b // [3]: // (s - t * u) * |m1| + t * |m0 - m1 * u| // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u) // = s * |m1| + t * |m0| <= b auto tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } // by [3]: |m0| <= b/g // by g != b: |m0| < b/g if (m0 < 0) m0 += b / s; return {s, m0}; } // Compile time primitive root // @param m must be prime // @return primitive root (and minimum in now) constexpr int primitive_root_constexpr(int m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; int x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (int i = 3; (long long)(i)*i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) { x /= i; } } } if (x > 1) { divs[cnt++] = x; } for (int g = 2;; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } template constexpr int primitive_root = primitive_root_constexpr(m); } // namespace internal void butterfly(std::vector& a) { static constexpr int g = internal::primitive_root; int n = int(a.size()); int h = internal::ceil_pow2(n); static bool first = true; static mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i] if (first) { first = false; mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1 int cnt2 = internal::bsf(mod - 1); mint e = mint(g).power((mod - 1) >> cnt2), ie = 1/e; for (int i = cnt2; i >= 2; i--) { // e^(2^i) == 1 es[i - 2] = e; ies[i - 2] = ie; e *= e; ie *= ie; } mint now = 1; for (int i = 0; i <= cnt2 - 2; i++) { sum_e[i] = es[i] * now; now *= ies[i]; } } for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1), p = 1 << (h - ph); mint now = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { auto l = a[i + offset]; auto r = a[i + offset + p] * now; a[i + offset] = l + r; a[i + offset + p] = l - r; } now *= sum_e[internal::bsf(~(unsigned int)(s))]; } } } void butterfly_inv(std::vector& a) { static constexpr int g = internal::primitive_root; int n = int(a.size()); int h = internal::ceil_pow2(n); static bool first = true; static mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i] if (first) { first = false; mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1 int cnt2 = internal::bsf(mod - 1); mint e = mint(g).power((mod - 1) >> cnt2), ie = 1/e; for (int i = cnt2; i >= 2; i--) { // e^(2^i) == 1 es[i - 2] = e; ies[i - 2] = ie; e *= e; ie *= ie; } mint now = 1; for (int i = 0; i <= cnt2 - 2; i++) { sum_ie[i] = ies[i] * now; now *= es[i]; } } for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1), p = 1 << (h - ph); mint inow = 1; for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); for (int i = 0; i < p; i++) { auto l = a[i + offset]; auto r = a[i + offset + p]; a[i + offset] = l + r; a[i + offset + p] = (unsigned long long)(mod + l.val - r.val) * inow.val; } inow *= sum_ie[internal::bsf(~(unsigned int)(s))]; } } } vectorntt(const vector&A,const vector&B){ auto a=A,b=B; int alen=a.size(); int blen=b.size(); int clen=alen+blen-1; int n=1; while(n<=clen)n*=2; int log=1; while((1<; poly p; FPS():p(){} explicit FPS(mint a):p(1,a){} FPS(poly p):p(p){} explicit FPS(int size,mint val):p(size,val){} int size() const { return int(p.size()); } mint&operator[](int i) { return p[i]; } FPS operator-() const { auto res=p; for(auto&x:res)x=-x; return res; } FPS&operator+=(const FPS& a) noexcept { if(p.size()>=(int i) noexcept { reverse(p.begin(),p.end()); while(i--)p.pop_back(); reverse(p.begin(),p.end()); return *this; } friend FPS operator +(const FPS&a,const FPS&b) noexcept{return FPS(a)+=b;} friend FPS operator -(const FPS&a,const FPS&b) noexcept{return FPS(a)-=b;} friend FPS operator *(const FPS&a,const FPS&b) noexcept{return FPS(a)*=b;} friend FPS operator /(const FPS&a,const FPS&b) noexcept{return FPS(a)/=b;} friend FPS operator +(const FPS&a,const mint&b) noexcept{return FPS(a)+=b;} friend FPS operator -(const FPS&a,const mint&b) noexcept{return FPS(a)-=b;} friend FPS operator *(const FPS&a,const mint&b) noexcept{return FPS(a)*=b;} friend FPS operator /(const FPS&a,const mint&b) noexcept{return FPS(a)/=b;} friend FPS operator <<(const FPS&a,const int i) noexcept{return FPS(a)<<=i;} friend FPS operator >>(const FPS&a,const int i) noexcept{return FPS(a)>>=i;} //前N項を抜き出す FPS&shrink(int n){ p.resize(n); return *this; } FPS shrinked(const FPS&a,int n) const { return FPS(a).shrink(n); } void push_back(const mint&a){ p.emplace_back(a); } void push_back(const FPS&a){ for(const auto&x:a.p)p.emplace_back(x); } void emplace_back(const mint&a){ p.emplace_back(a); } void emplace_back(const FPS&a){ for(const auto&x:a.p)p.emplace_back(x); } FPS inv(long long a=-1) const { if(a==-1)a=p.size(); assert(p[0]!=0); FPS res(1/p[0]); for(int i=1;;i++){ if((1<<(i-1))>a)break; auto f=shrinked(*this,1<>=(1<<(i-1)); h=-h*res; for(int j=0;j<(1<<(i-1));j++)res.p.emplace_back(h[j]); } res.shrink(a); return FPS(res); } FPS diff() const { auto res=*this; for(int i=0;i>=1; return res; } FPS integral() const { int n=size(); FPS ret(n+1,0); if(n>0)ret[1]=1; for(int i=2;i<=n;i++)ret[i]=-ret[mod%i]*(mod/i); for(int i=0;isync_with_stdio(0); pass_time=clock(); int t=1; //cin>>t; while(t--)solve(); pass_time=clock()-pass_time; dbg(pass_time/CLOCKS_PER_SEC); }