#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;

const int MAXN = 30;
const int MAXE = 10000 + 100;
const int MOD = 1163962801;
const int PRIM_ROOT = 46;
const int MAX_LOG = 30;

int x[MAXE];
int y[MAXE];
int a[MAXE];
int b[MAXE];
int n;
int m;
int t;
int pgx[MAXN];
int pgy[MAXN];
int d[MAXN][MAXN];
int ret[MAXN][MAXN];
int z[MAXN][MAXN];
int ans[MAXN][MAXN];
int v[MAXN][MAXN][MAXN][MAXN];

int power (int a, int p) {
    if (p == 0)
        return 1;
    if (p == 1)
        return a % MOD;
    if (p & 1)
        return power(a, p - 1) * 1LL * a % MOD;
    int q = power(a, p / 2);
    return q * 1LL * q % MOD;
}

int getInverse (int a) {
    return power(a, MOD - 2);
}

void mulMatrix (int a[MAXN][MAXN], int b[MAXN][MAXN], int c[MAXN][MAXN]) {
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            d[i][j] = 0;
            for(int k = 0; k < n; k++) {
                d[i][j] = (d[i][j] + a[i][k] * 1LL * b[k][j]) % MOD;
            }
        }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            c[i][j] = d[i][j];
}

void fillAt (int xx, int yy) {
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            z[i][j] = 0;
    for (int i = 0; i < m; i++)
        z[x[i]][y[i]] = (z[x[i]][y[i]] + pgx[a[i] * xx % n] * 1LL * pgy[b[i] * yy % (n - 1)]) % MOD;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            ret[i][j] = (int)(i == j);
    for(int i = 0; i <= MAX_LOG; i++) {
        if (t & (1 << i))
            mulMatrix(ret, z, ret);
        mulMatrix(z, z, z);
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            v[i][j][xx][yy] = ret[i][j];
}

void getAnswer (int x, int y) {
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            ans[i][j] = 0;
    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++) {
                    ans[i][j] = (ans[i][j] + v[x][y][k][l] * 1LL * pgx[n - i * k % n] % MOD * 1LL * pgy[n - 1 - j * l % (n - 1)] % MOD) % MOD;
                }
            }
            ans[i][j] = ans[i][j] * 1LL * getInverse(n * (n - 1)) % MOD;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 2; j++)
            cout << ans[i][j] << " ";
        cout << ans[i][n - 2] << endl;
    }
}

int main() {
    cin >> n >> m >> t;
    assert(1 <= n && n <= 22);
    assert(1 <= m && m <= 10000);
    assert(1 <= t && t <= 1000000000);
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i] >> a[i] >> b[i];
        assert(1 <= x[i] && x[i] <= n);
        assert(1 <= y[i] && y[i] <= n);
        assert(990 <= 0.99 * a[i] && 0.99 * a[i] <= b[i] && b[i] <= a[i] && a[i] <= 10000000);
        --x[i];
        --y[i];
        a[i] %= n;
        b[i] %= n - 1;
    }
    int gx = power(PRIM_ROOT, (MOD - 1) / n), gy = power(PRIM_ROOT, (MOD - 1) / (n - 1));
    pgx[0] = pgy[0] = 1;
    for (int i = 1; i <= n; i++) {
        pgx[i] = pgx[i - 1] * 1LL * gx % MOD;
        pgy[i] = pgy[i - 1] * 1LL * gy % MOD;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n - 1; j++)
            fillAt(i, j);
    for (int i = 0; i < n; i++)
        getAnswer(i, i);
    return 0;
}