rt.

#include<bits/stdc++.h>
using namespace std;
#define mod 2017
#define il inline
#define re register

il int read(){
	int s=0,w=1;char c=getchar();
	while(!isdigit(c)){ if(c=='-') w=-1;c=getchar();}
	while(isdigit(c)){ s=(s<<3)+(s<<1)+(c^48);c=getchar();};
	return s*w;
}

#define N 1000005
int n,m,e,to[1000],ne[1000],h[1000];
int dp[N][32];

il void add(re int x,re int y){
	to[++e]=y,ne[e]=h[x],h[x]=e;
}

int T;

signed main(){
	n=read(),m=read();
	for(re int i=1;i<=m;++i){
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	for(re int i=1;i<=n;++i) add(i,n+1);
	for(re int i=1;i<=n+1;++i) add(i,i);
	
	T=read();
	
	dp[1][0]=1;
	for(re int t=0;t<=T;++t){
		for(re int x=1;x<=n+1;++x){
			for(re int j=h[x];j;j=ne[j]){
				int y=to[j];
				dp[y][t+1]+=dp[x][t];
				dp[y][t+1]%=mod;
			}
		}
	}
	
	int ans=0;
	for(int i=1;i<=n+1;i++){
		ans=(ans+dp[i][T])%mod;
	}
	
	printf("%d\n",ans);
	
	return 0;
}