#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template ostream& operator<<(ostream &os, const pair &p) { return os << '(' << p.first << ", " << p.second << ')'; } template::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector vi; typedef vector vvi; typedef pair pi; const int mxN = 1e5+1, oo = 1e9; const ll mod = 998244353; #define rep(i,a,b) for(int i=a;i struct mdint { int d=0; mdint () {d=0;} mdint (long long _d) : d(_d%MOD){ if(d<0) d+=MOD; }; friend mdint& operator+=(mdint& a, const mdint& o) { a.d+=o.d; if(a.d>=MOD) a.d-=MOD; return a; } friend mdint& operator-=(mdint& a, const mdint& o) { a.d-=o.d; if(a.d<0) a.d+=MOD; return a; } friend mdint& operator*=(mdint& a, const mdint& o) { return a = mdint((ll)a.d*o.d); } mdint operator*(const mdint& o) const { mdint res = *this; res*=o; return res; } mdint operator+(const mdint& o) const { mdint res = *this; res+=o; return res; } mdint operator-(const mdint& o) const { mdint res = *this; res-=o; return res; } mdint operator^(long long b) const { mdint tmp = 1; mdint power = *this; while(b) { if(b&1) { tmp = tmp*power; } power = power*power; b/=2; } return tmp; } friend mdint operator/=(mdint& a, const mdint& o) { a *= (o^(MOD-2)); return a; } mdint operator/(const mdint& o) { mdint res = *this; res/=o; return res; } bool operator==(const mdint& o) { return d==o.d;} bool operator!=(const mdint& o) { return d!=o.d;} friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;} friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;} }; using mint = mdint; ll det(vector>& a) { int n = a.size(); ll ans = 1; rep(i,0,n) { rep(j,i+1,n) { while (a[j][i] != 0) { // gcd step ll t = a[i][i] / a[j][i]; if (t) rep(k,i,n) a[i][k] = (a[i][k] - a[j][k] * t) % mod; swap(a[i], a[j]); ans *= -1; } } ans = ans * a[i][i] % mod; if (!ans) return 0; } return (ans + mod) % mod; } int main() { // calculate reduced form and multiply // need polynomials int n; cin >> n; vvi a(n,vi(n)); for(auto& r : a) for(auto& i : r) cin >> i; vvi b(n,vi(n)); for(auto& r : b) for(auto& i : r) cin >> i; vector dets; for(int x=0;x<=n;++x) { vector> ab(n,vector(n)); for(int i=0;i res(n+1); for(int i=0;i<=n;++i) { vector> pols; auto mul = [&pols](auto self, int l, int r) { if(l==r) return pols[l]; int mid = (l+r)/2; auto c = self(self,l,mid), d = self(self,mid+1,r); vector res(c.size()+d.size()-1); for(int i=0;i{-j,1}); denum*=i-j; } auto mypol = mul(mul,0,n-1); for(int j=0;j