#include <bits/stdc++.h>
using namespace std;
#define MAX 101
const int MOD = 1e9 + 7;
struct Matrix
{
unsigned long long M[MAX][MAX];
Matrix operator * (Matrix &a)
{
Matrix ans;
memset(ans.M, 0, sizeof ans.M);
for(int i = 0; i < MAX; i++)
for(int j = 0; j < MAX; j++)
for(int k = 0; k < MAX; k++)
ans.M[i][j] = (ans.M[i][j] + (M[i][k] * a.M[k][j]) % MOD) % MOD;
return ans;
}
Matrix pow(int p)
{
Matrix ans, b = *this;
for(int i = 0; i < MAX; i++)
for(int j = 0; j < MAX; j++)
ans.M[i][j] = (i == j);
while(p)
{
if(p & 1)
ans = ans * b;
p >>= 1;
b = b * b;
}
return ans;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,r,k,x,y;
cin>>n>>r>>k;
Matrix m;
for(int i=0;i<r;i++)
{
cin>>x>>y;
m.M[x-1][y-1]+=1LL;
m.M[y-1][x-1]+=1LL;
}
m=m.pow(k);
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(j!=i+1)
cout<<" ";
if(m.M[i][j]==0)
cout<<-1;
else
cout<<m.M[i][j];
}
cout<<"\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIE1BWCAxMDEKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7CnN0cnVjdCBNYXRyaXgKewoJdW5zaWduZWQgbG9uZyBsb25nIE1bTUFYXVtNQVhdOwoJTWF0cml4IG9wZXJhdG9yICogKE1hdHJpeCAmYSkgCgl7CgkJTWF0cml4IGFuczsKCQltZW1zZXQoYW5zLk0sIDAsIHNpemVvZiBhbnMuTSk7CgkJZm9yKGludCBpID0gMDsgaSA8IE1BWDsgaSsrKQoJCQlmb3IoaW50IGogPSAwOyBqIDwgTUFYOyBqKyspCgkJCQlmb3IoaW50IGsgPSAwOyBrIDwgTUFYOyBrKyspCgkJCQkJYW5zLk1baV1bal0gPSAoYW5zLk1baV1bal0gKyAoTVtpXVtrXSAqIGEuTVtrXVtqXSkgJSBNT0QpICUgTU9EOwoJCXJldHVybiBhbnM7Cgl9CglNYXRyaXggcG93KGludCBwKQoJewoJCU1hdHJpeCBhbnMsIGIgPSAqdGhpczsKCQlmb3IoaW50IGkgPSAwOyBpIDwgTUFYOyBpKyspCgkJCWZvcihpbnQgaiA9IDA7IGogPCBNQVg7IGorKykKCQkJYW5zLk1baV1bal0gPSAoaSA9PSBqKTsKCQl3aGlsZShwKQoJCXsKCQkJaWYocCAmIDEpCgkJCWFucyA9IGFucyAqIGI7CgkJCXAgPj49IDE7CgkJCWIgPSBiICogYjsKCQl9CgkJcmV0dXJuIGFuczsKCX0KfTsKCmludCBtYWluKCkgewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKDApOwoJY291dC50aWUoMCk7CglpbnQgbixyLGsseCx5OwoJY2luPj5uPj5yPj5rOwoJTWF0cml4IG07Cglmb3IoaW50IGk9MDtpPHI7aSsrKQoJewoJCWNpbj4+eD4+eTsKCQltLk1beC0xXVt5LTFdKz0xTEw7CgkJbS5NW3ktMV1beC0xXSs9MUxMOwoJfQoJbT1tLnBvdyhrKTsKCWZvcihpbnQgaT0wO2k8bjtpKyspCgl7CgkJZm9yKGludCBqPWkrMTtqPG47aisrKQoJCXsKCQkJaWYoaiE9aSsxKQoJCQkJY291dDw8IiAiOwoJCQlpZihtLk1baV1bal09PTApCgkJCQljb3V0PDwtMTsKCQkJZWxzZQoJCQkJY291dDw8bS5NW2ldW2pdOwoJCX0KCQkJCgkJY291dDw8IlxuIjsKCX0KCQkKCXJldHVybiAwOwp9