分析：
太忙（lan）了不想写，附我看的链接
https://www.cnblogs.com/ivorysi/p/8868453.html
#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 25
#define MAXM 10010
#define MOD 1163962801
using namespace std;
typedef long long ll;
ll px[MAXN],py[MAXN],v1[MAXM],v2[MAXM],w[MAXN][MAXN],v[MAXN][MAXN][MAXN][MAXN];
int st[MAXM],ed[MAXM];
const ll G=46;
int N,M;
ll T;
struct Matrix{
ll a[MAXN][MAXN];Matrix operator * (const Matrix &b) const {
Matrix c;c.clear();for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<N;k++)c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%MOD)%MOD;return c;} void clear(){
memset(a,0,sizeof a); }void Setup(int x,int y){
clear();for(int i=0;i<M;i++)a[st[i]][ed[i]]=(a[st[i]][ed[i]]+px[v1[i]*x%N]*py[v2[i]*y%(N-1)]%MOD)%MOD;}
}I,Ans;
ll fsp(ll x,ll y){
ll res=1;while(y){
if(y&1ll)res=res*x%MOD;x=x*x%MOD;y>>=1ll; }return res;
}
void fspM(ll y){
Ans.clear();for(int i=0;i<N;i++)Ans.a[i][i]=1;while(y){
if(y&1ll)Ans=Ans*I;I=I*I;y>>=1ll;}
}
void Prepare(){
SF("%d%d%lld",&N,&M,&T);for(int i=0;i<M;i++){
SF("%d%d%lld%lld",&st[i],&ed[i],&v1[i],&v2[i]);st[i]--;ed[i]--;v1[i]%=N;v2[i]%=(N-1);}px[0]=1;py[0]=1;px[1]=fsp(G,(MOD-1)/N);py[1]=fsp(G,(MOD-1)/(N-1));for(int i=2;i<=N;i++)px[i]=px[i-1]*px[1]%MOD;for(int i=2;i<=N-1;i++)py[i]=py[i-1]*py[1]%MOD;
}
void DFT1(int x){
for(int i=0;i<N;i++)for(int j=0;j<N-1;j++){
w[i][j]=0;for(int k=0;k<N;k++)for(int l=0;l<N-1;l++)w[i][j]=(w[i][j]+v[x][x][k][l]*px[N-i*k%N]%MOD*py[N-1-j*l%(N-1)]%MOD)%MOD;w[i][j]=w[i][j]*fsp(N*(N-1),MOD-2)%MOD;}
}
int main(){
Prepare();for(int i=0;i<N;i++)for(int j=0;j<N-1;j++){
I.Setup(i,j);fspM(T);for(int k=0;k<N;k++)for(int l=0;l<N;l++)v[k][l][i][j]=Ans.a[k][l];}for(int i=0;i<N;i++){
DFT1(i); for(int j=0;j<N;j++){
for(int k=0;k<N-1;k++)PF("%lld ",w[j][k]);PF("\n");}}
}