#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 22;
const int NN = N * (N - 1);
unsigned p = 1163962801, pr = 46, prx, pry;
unsigned ppx[N], ppy[N];
//int p = 232792561, pr = 71;
int n, nn, m, t;
struct {int s, t, x, y;} e[10020];
unsigned z[N][N], v[N][N][N][N], w[N][N], r[N][N];
unsigned pw(unsigned x, unsigned y) {
	unsigned re = 1;
	for (; y > 0; y >>= 1) {
		if (y & 1) {
			re = (long long)re * x % p;
		}
		x = (long long)x * x % p;
	}
	return re;
}

void gen(int x, int y) {
	memset(z, 0, sizeof z);
	for (int i = 0; i < m; i++) {
		z[e[i].s][e[i].t] = (z[e[i].s][e[i].t] + (long long)ppx[e[i].x * x % n] * ppy[e[i].y * y % (n - 1)]) % p;
	}
}

void mul(unsigned a[N][N], unsigned b[N][N], unsigned c[N][N]) {
	unsigned re[N][N] = {};
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < n; k++) {
			if (a[i][k] == 0) {
				continue;
			}
			for (int j = 0; j < n; j++) {
				re[i][j] = (re[i][j] + (long long)a[i][k] * b[k][j]) % p;
			}
		}
	}
	memcpy(c, re, sizeof re);
}

void matrix(int x, int y) {
	int u = t;
	memset(r, 0, sizeof r);
	for (int i = 0; i < n; i++) {
		r[i][i] = 1;
	}
	while (true) {
		if (u & 1) {
			mul(r, z, r);
		}
		u >>= 1;
		if (u == 0) {
			break;
		}
		mul(z, z, z);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			v[i][j][x][y] = r[i][j];
		}
	}
}

void solve(int x, int y) {
	memset(w, 0, sizeof w);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			for (int k = 0; k < n; k++) {
				for (int l = 0; l < n - 1; l++) {
					w[i][j] = (w[i][j] + (long long)v[x][y][k][l] * ppx[n - i * k % n] % p * ppy[n - 1 - j * l % (n - 1)] % p) % p;

				}
			}
			w[i][j] = (long long)w[i][j] * pw(n * (n - 1), p - 2) % p;
		}
	}
	return;
}

void print() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			printf("%u%c", w[i][j], j == n - 2 ? '\n' : ' ');
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &t);
	nn = n * (n - 1);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d%d", &e[i].s, &e[i].t, &e[i].x, &e[i].y);
		e[i].s -= 1;
		e[i].t -= 1;
		e[i].x %= n;
		e[i].y %= n - 1;
	}

	prx = pw(pr, (p - 1) / n);
	pry = pw(pr, (p - 1) / (n - 1));

	ppx[0] = ppy[0] = 1;
	for (int i = 1; i <= n; i++) {
		ppx[i] = (long long)ppx[i - 1] * prx % p;
	}

	for (int i = 1; i <= n - 1; i++) {
		ppy[i] = (long long)ppy[i - 1] * pry % p;
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - 1; j++) {
			gen(i, j);
			matrix(i, j);
		}
	}

	for (int i = 0; i < n; i++) {
		solve(i, i);
		print();
	}
	return 0;
}