#include <bits/stdc++.h>
using namespace std;
#define MOD 2017

int n, m, u, v, t, ans;
int A[31][31], C[31][31], E[31][31];

void mul(int A[31][31], int B[31][31]){
	memset(C, 0, sizeof(C));
	
	for (int i=0; i<=n; i++){
		for (int j=0; j<=n; j++){
			for (int k=0; k<=n; k++) C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
		}
	}
	
	memcpy(A, C, sizeof(C));
}

void qpow(int A[31][31], int k){
	memset(E, 0, sizeof(E));
	for (int i=1; i<=30; i++) E[i][i] = 1;
	
	while (k){
		if (k & 1) mul(E, A);
		mul(A, A);
		k >>= 1;
	}
	
	memcpy(A, E, sizeof(E));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for (int i=1; i<=m; i++){
		cin >> u >> v;
		A[u][v] = A[v][u] = 1;
	}
	for (int i=0; i<=n; i++) A[i][i] = A[0][i] = 1;
	
	for (int i=0; i<=n; i++){
		for (int j=0; j<=n; j++){
			cout << A[i][j] << ' ';
		}
		cout << '\n';
	}
	
	cin >> t;
	qpow(A, t);
	for (int i=0; i<=n; i++) ans = (ans + A[1][i]) % MOD;
	
	cout << ans;
	
	return 0;
}