ACC

#include<bits/stdc++.h>
using namespace std;
int ans[120],t2[120];
int mod=2027;
int mat[120][120],t1[120][120];
int main() {
	int n,m;
	cin>>n>>m;
	ans[1]=1;
	mat[0][0]=1;//开始就自爆
	for(int i=1; i<=n; i++) {//n和m不一样不能丢下面
		mat[i][0]=1;//每个城市自爆
		mat[i][i]=1;//停留原地
	}
	for(int i=0; i<m; i++) {
		int u,v;
		cin>>u>>v;
		   mat[u][v]=mat[v][u]=1;//路路通
	}
	int t;
	cin>>t;
	while(t) {//你要加1，因为它会爆
		if(t&1) {
			memset(t2,0,sizeof t2);
			for(int i=0; i<n+1; i++) {
				for(int j=0; j<n+1; j++) {
					t2[j]+=mat[i][j]*ans[i]%mod;
				}
			}
			for(int i=0; i<n+1; i++) {
				ans[i]=t2[i]%mod;
			}
		}
		t>>=1;
		memset(t1,0,sizeof t1);
		for(int i=0; i<n+1; i++) {
			for(int j=0; j<n+1; j++) {
				for(int k=0; k<n+1; k++) {
					t1[i][k]+=mat[i][j]*mat[j][k]%mod;
				}
			}
		}
		for(int i=0; i<n+1; i++) {
			for(int j=0; j<n+1; j++) {
				mat[i][j]=t1[i][j]%mod;
			}
		}
	}
	int sum=0;
	for(int i=0; i<=n+1; i++) {
		sum=(sum+ans[i])%mod;
	}
	cout<<sum;
	return 0;
}