#include<bits/stdc++.h>
#define ll long long
#define p 1000000009
#define N 130
#define w3 115381398ll
using namespace std;
int n,m,x,y,bz[N];
ll c[N][N],f[N][N],a[N][N],g[N][N],k,h[N][N][N];
void add(ll &x,ll y){x+=y;if(x>=p)x-=p;}
void solve(ll w){
	memset(g,0,sizeof(g));
	for(int i=0;i<=n;i++){ll v=w*w%p;
		memset(f,0,sizeof(f));f[0][0]=1;
		for(int j=1;j<=n-i;j++)
		for(int x=n;x>=0;x--)
		for(int y=n-x;y>=0;y--){
			if(x)add(f[x][y],f[x-1][y]);
			if(y)add(f[x][y],f[x][y-1]);
		}
		for(int j=1;j<=i;j++)
		for(int x=n;x>=0;x--)
		for(int y=n-x;y>=0;y--){
			if(x)f[x][y]=(f[x][y]+f[x-1][y]*w);
			if(y)f[x][y]=(f[x][y]+f[x][y-1]*v);
			f[x][y]%=p;
		}
		for(int x=0;x<=n;x++)
		for(int y=0;y<=n-x;y++)
		add(g[i][0],1ll*a[x][y]*f[x][y]%p);
		for(int j=1;j<=n-i;j++){
			for(int x=n;x>=0;x--)
			for(int y=n-x;y>=0;y--){
				if(x)f[x][y]+=f[x-1][y]*v;
				if(y)f[x][y]+=f[x][y-1]*w;
				f[x][y]%=p;
			}
			for(int x=0;x<=n;x++)
			for(int y=0;y<=n-x;y++){
				if(x)add(f[x][y],p-f[x-1][y]);
				if(y)add(f[x][y],p-f[x][y-1]);
			}
			for(int x=0;x<=n;x++)
			for(int y=0;y<=n-x;y++)
			g[i][j]=(g[i][j]+a[x][y]*f[x][y])%p;
		}
	}
}
ll qpow(ll x,ll v){
	ll y=1;
	while(v){
		if(v&1)y=y*x%p;
		x=x*x%p;v>>=1;
	}return y;
}
int main(){
//	freopen("machine.in","r",stdin);
//	freopen("machine.out","w",stdout);
	scanf("%d%d%lld",&n,&m,&k);
	for(int i=0;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		a[x][y]++;
	}
	solve(w3);
	for(int i=0;i<=n;i++)
	for(int j=0;j<=n-i;j++)
	a[i][j]=qpow(g[i][j],k%(p-1));
	solve(1ll*w3*w3%p);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n-i;j++){
			g[i][j]=1ll*g[i][j]*qpow(qpow(3,n),p-2)%p*c[n][i]%p*c[n-i][j]%p;
			printf("%lld ",g[i][j]);
		}printf("\n");
	}
}