#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace __gnu_pbds; #define all(x) (x).begin(), (x).end() #define pb push_back #define eb emplace_back #define xx first #define yy second #define sz(x) (int)(x).size() #define gc getchar #define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define mp make_pair #define ins insert #ifndef ONLINE_JUDGE # define LOG(x) (cerr << #x << " = " << (x) << endl) #else # define LOG(x) ((void)0) #endif using ll = long long; using ull = unsigned long long ; using ld = long double ; using str = string; using ordered_set=tree, null_type, less>, rb_tree_tag, tree_order_statistics_node_update>; const double PI=acos(-1); const ll INF = 1LL<<62; const ll MINF = -(1LL<<62); template T getint() { T val=0; char c; bool neg=false; while((c=gc()) && !(c>='0' && c<='9')) { neg|=c=='-'; } do { val=(val*10)+c-'0'; } while((c=gc()) && (c>='0' && c<='9')); return val*(neg?-1:1); } //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution(0, n-1)(rng) const ll mod=998244353; template struct modular { int64_t r; modular() : r(0) {} modular(int64_t rr) : r(rr) {if(abs(r) >= m) r %= m; if(r < 0) r += m;} modular inv() const {return bpow(*this, m - 2);} modular operator * (const modular &t) const {return (r * t.r) % m;} modular operator / (const modular &t) const {return *this * t.inv();} modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;} modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;} modular operator + (const modular &t) const {return modular(*this) += t;} modular operator - (const modular &t) const {return modular(*this) -= t;} modular operator *= (const modular &t) {return *this = *this * t;} modular operator /= (const modular &t) {return *this = *this / t;} bool operator == (const modular &t) const {return r == t.r;} bool operator != (const modular &t) const {return r != t.r;} operator int64_t() const {return r;} int64_t bpow(int64_t a, int64_t b) const { int64_t res=1; while(b) { if(b&1) res=(res*a)%m; a=(a*a)%m; b/=2; } return res; } }; using Mint = modular; using matrix = vector>; ostream& operator<<(ostream& os, matrix M) { for(auto& i:M) { for(auto& j:i) { os< char_poly(matrix& M) { const int n=sz(M); make_upper_heisenberg(M); vector> p(n+1); p[0]={1}; //det(Ix-M) //kifejtés miatt: P[i+1]=1*(-P[i]*M(i,i)+xP[i])-\sum j=0..i-1 (P[j]*M(j,i)* prod M(j+1..i,j..i-1)) for(int i=0;i=0;j--) { mul*=M[j+1][j]; Mint hb=-M[j][i]*mul; for(int k=0;k det_linear(matrix M0, matrix M1) { //sor és oszlop műveletekkel M1-et I-vé transzformáljuk det(M0+M1x)=1/(det(A)*det(B))*det(Ix+AM0B) alakra hozzuk => -AM0B karakterisztikus polinomja a megoldás //ha nem reguláris M1 "M0-ból hozunk át oszlopokat" const int N=M0.size(); Mint invdetAB=1; int powx=0; for(int p=0;pN) return vector(N+1); for(int i=0;i{998244351,998244348,1})); //~ for(auto i:char_poly(m)) cerr<>n; //~ matrix m(n); //~ for(int i=0;i>x; //~ m[i][j]=x; //~ } //~ } //~ for(auto i:char_poly(m)) { //~ cout<>n; matrix M0(n), M1(n); for(int i=0;i>x; M0[i][j]=x; } } for(int i=0;i>x; M1[i][j]=x; } } for(auto i:det_linear(M0, M1)) cout<