#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second int n,M; namespace S1{ const int M=1e9+7; int s[710],is[710]; int p[710][710],d[710][710]; int T[710][710],IT[710][710]; int b[710]; pii B[710]; pii x[710]; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline int inv(int x){return qp(x,M-2);} inline void add(int &x,int y){ if((x+=y)>=M)x-=M; } inline void slv(){ for(int i=1;i<=n+1;i++) for(int j=1;j<i;j++) cin>>d[i][j],d[j][i]=d[i][j]; for(int i=1;i<=n+1;i++) for(int j=1;j<i;j++) cin>>p[i][j],p[j][i]=p[i][j]; for(int i=1;i<=n;i++){ for(int j=1;j<=n+1;j++) add(s[i],p[i][j]); is[i]=inv(s[i]); T[i][i]=1; for(int j=1;j<=n+1;j++) if(p[i][j])T[i][j]=M-(p[i][j]*is[i]%M),add(b[i],p[i][j]*is[i]%M*d[i][j]%M); } for(int i=1;i<=n;i++)IT[i][i]=1; for(int i=1;i<=n;i++){ int p=i; if(!T[i][i]){ for(int j=i+1;j<=n;j++) if(T[i][j])p=j; for(int j=1;j<=n;j++) swap(T[i][j],T[p][j]), swap(IT[i][j],IT[p][j]); } int IV=inv(T[i][i]); for(int j=1;j<=n;j++) T[i][j]=T[i][j]*IV%M, IT[i][j]=IT[i][j]*IV%M; for(int j=1;j<=n;j++) if(i!=j){ int p=T[j][i]; int *g1=T[j],*g2=T[i]; int *f1=IT[j],*f2=IT[i]; for(int k=1;k<=n;k++) g1[k]=(g1[k]-g2[k]*p)%M, f1[k]=(f1[k]-f2[k]*p)%M; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) IT[i][j]=(IT[i][j]+M)%M; // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // for(int k=1;k<=n;k++) // add(A[i][k],CT[i][j]*IT[j][k]%M); // for(int i=1;i<=n;i++,cout<<endl) // for(int j=1;j<=n;j++) // cout<<A[i][j]<<" "; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(i==j)B[j]={1,0}; else B[j]={0,b[j]}; for(int i=1;i<=n;i++){ pii e={0,0}; int *g=IT[i]; for(int j=1;j<=n;j++){ p1(e)+=g[j]*p1(B[j])%M; p2(e)+=IT[i][j]*p2(B[j])%M; } p1(e)%=M,p2(e)%=M; x[i]=e; } int xv=(M-p2(x[i]))*inv(p1(x[i]))%M; // for(int i=1;i<=n;i++) // cout<<p1(x[i])<<"x+"<<p2(x[i])<<" "; // cout<<endl; for(int i=1;i<=n;i++) printf("%lld ",(p1(x[i])*xv%M+p2(x[i]))%M); printf("\n"); } } } namespace S2{ const int M=1e9+9; int s[710],is[710]; int p[710][710],d[710][710]; int T[710][710],IT[710][710]; int b[710]; pii B[710]; pii x[710]; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline int inv(int x){return qp(x,M-2);} inline void add(int &x,int y){ if((x+=y)>=M)x-=M; } inline void slv(){ for(int i=1;i<=n+1;i++) for(int j=1;j<i;j++) cin>>d[i][j],d[j][i]=d[i][j]; for(int i=1;i<=n+1;i++) for(int j=1;j<i;j++) cin>>p[i][j],p[j][i]=p[i][j]; for(int i=1;i<=n;i++){ for(int j=1;j<=n+1;j++) add(s[i],p[i][j]); is[i]=inv(s[i]); T[i][i]=1; for(int j=1;j<=n+1;j++) if(p[i][j])T[i][j]=M-(p[i][j]*is[i]%M),add(b[i],p[i][j]*is[i]%M*d[i][j]%M); } for(int i=1;i<=n;i++)IT[i][i]=1; for(int i=1;i<=n;i++){ int p=i; if(!T[i][i]){ for(int j=i+1;j<=n;j++) if(T[i][j])p=j; for(int j=1;j<=n;j++) swap(T[i][j],T[p][j]), swap(IT[i][j],IT[p][j]); } int IV=inv(T[i][i]); for(int j=1;j<=n;j++) T[i][j]=T[i][j]*IV%M, IT[i][j]=IT[i][j]*IV%M; for(int j=1;j<=n;j++) if(i!=j){ int p=T[j][i]; int *g1=T[j],*g2=T[i]; int *f1=IT[j],*f2=IT[i]; for(int k=1;k<=n;k++) g1[k]=(g1[k]-g2[k]*p)%M, f1[k]=(f1[k]-f2[k]*p)%M; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) IT[i][j]=(IT[i][j]+M)%M; // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // for(int k=1;k<=n;k++) // add(A[i][k],CT[i][j]*IT[j][k]%M); // for(int i=1;i<=n;i++,cout<<endl) // for(int j=1;j<=n;j++) // cout<<A[i][j]<<" "; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(i==j)B[j]={1,0}; else B[j]={0,b[j]}; for(int i=1;i<=n;i++){ pii e={0,0}; int *g=IT[i]; for(int j=1;j<=n;j++){ p1(e)+=g[j]*p1(B[j])%M; p2(e)+=IT[i][j]*p2(B[j])%M; } p1(e)%=M,p2(e)%=M; x[i]=e; } int xv=(M-p2(x[i]))*inv(p1(x[i]))%M; // for(int i=1;i<=n;i++) // cout<<p1(x[i])<<"x+"<<p2(x[i])<<" "; // cout<<endl; for(int i=1;i<=n;i++) printf("%lld ",(p1(x[i])*xv%M+p2(x[i]))%M); printf("\n"); } } } namespace S3{ const int M=998244353; int s[710],is[710]; int p[710][710],d[710][710]; int T[710][710],IT[710][710]; int b[710]; pii B[710]; pii x[710]; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline int inv(int x){return qp(x,M-2);} inline void add(int &x,int y){ if((x+=y)>=M)x-=M; } inline void slv(){ for(int i=1;i<=n+1;i++) for(int j=1;j<i;j++) cin>>d[i][j],d[j][i]=d[i][j]; for(int i=1;i<=n+1;i++) for(int j=1;j<i;j++) cin>>p[i][j],p[j][i]=p[i][j]; for(int i=1;i<=n;i++){ for(int j=1;j<=n+1;j++) add(s[i],p[i][j]); is[i]=inv(s[i]); T[i][i]=1; for(int j=1;j<=n+1;j++) if(p[i][j])T[i][j]=M-(p[i][j]*is[i]%M),add(b[i],p[i][j]*is[i]%M*d[i][j]%M); } for(int i=1;i<=n;i++)IT[i][i]=1; for(int i=1;i<=n;i++){ int p=i; if(!T[i][i]){ for(int j=i+1;j<=n;j++) if(T[i][j])p=j; for(int j=1;j<=n;j++) swap(T[i][j],T[p][j]), swap(IT[i][j],IT[p][j]); } int IV=inv(T[i][i]); for(int j=1;j<=n;j++) T[i][j]=T[i][j]*IV%M, IT[i][j]=IT[i][j]*IV%M; for(int j=1;j<=n;j++) if(i!=j){ int p=T[j][i]; int *g1=T[j],*g2=T[i]; int *f1=IT[j],*f2=IT[i]; for(int k=1;k<=n;k++) g1[k]=(g1[k]-g2[k]*p)%M, f1[k]=(f1[k]-f2[k]*p)%M; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) IT[i][j]=(IT[i][j]+M)%M; // for(int i=1;i<=n;i++) // for(int j=1;j<=n;j++) // for(int k=1;k<=n;k++) // add(A[i][k],CT[i][j]*IT[j][k]%M); // for(int i=1;i<=n;i++,cout<<endl) // for(int j=1;j<=n;j++) // cout<<A[i][j]<<" "; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(i==j)B[j]={1,0}; else B[j]={0,b[j]}; for(int i=1;i<=n;i++){ pii e={0,0}; int *g=IT[i]; for(int j=1;j<=n;j++){ p1(e)+=g[j]*p1(B[j])%M; p2(e)+=IT[i][j]*p2(B[j])%M; } p1(e)%=M,p2(e)%=M; x[i]=e; } int xv=(M-p2(x[i]))*inv(p1(x[i]))%M; // for(int i=1;i<=n;i++) // cout<<p1(x[i])<<"x+"<<p2(x[i])<<" "; // cout<<endl; for(int i=1;i<=n;i++) printf("%lld ",(p1(x[i])*xv%M+p2(x[i]))%M); printf("\n"); } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // int C=clock(); // freopen("genshin.in","r",stdin); // freopen("genshin.out","w",stdout); cin>>n>>M; if(M==1e9+7)S1::slv(); else if(M==1e9+9)S2::slv(); else S3::slv(); // cerr<<(clock()-C)*1000/CLOCKS_PER_SEC<<endl; cout.flush(); return 0; }