#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m,t;
struct edge{
	int x,y,w;
	bool operator ==(edge a) const
	{
		return a.x==x&&a.y==y;
	}
};
vector<edge> ma,ans;
void pout(vector<edge> x)
{
	for(int i=0;i<x.size();i++) cout << x[i].x << ' ' << x[i].y << ' ' << x[i].w << '\n';
	cout << '\n';
	cout << '\n';
}
bool cmpx(edge x,edge y)
{
	if(x.x==y.x) return x.y<y.y;
	return x.x<y.x;
}
bool cmpy(edge x,edge y)
{
	if(x.y==y.y) return x.x<y.x;
	return x.y<y.y;
}
void dedup(vector<edge> &a)
{
	vector<edge> b=a;
	sort(b.begin(),b.end(),cmpx);
	a.clear();
	int i=0;
	while(i<b.size())
	{
		int k=a.size();
		a.push_back(b[i++]);
		while(i<b.size()&&a[k]==b[i]) a[k].w=(a[k].w+b[i++].w)%2017;
		if(!a[k].w)a.pop_back();
	}
	sort(a.begin(),a.end(),cmpx);
}
void mult(vector<edge> a,vector<edge> b,vector<edge> &c)
{
	c.clear();
	sort(a.begin(),a.end(),cmpy);
	sort(b.begin(),b.end(),cmpx);
	int i1=0,i2=0,j1=0,j2=0;
	while(i1<a.size()&&j1<b.size())
	{
		while(i1<a.size()&&j1<b.size()&&b[j1].x!=a[i1].y)
		{
			while(i1<a.size()&&b[j1].x>a[i1].y) i1++;
			while(j1<b.size()&&b[j1].x<a[i1].y) j1++;
		}
		j2=j1,i2=i1;
		while(i2<a.size()&&a[i1].y==a[i2].y) i2++;
		while(j2<b.size()&&b[j1].x==b[j2].x) j2++;
		for(int i=i1;i<i2;i++) 
		{
			for(int j=j1;j<j2;j++) 
			{
				c.push_back(edge{a[i].x,b[j].y,(a[i].w*b[j].w)%2017});
			}
		}
//		pout(c);
		i1=i2,j1=j2;
	}
//	cout << "OKM" << endl; 
	dedup(c);
}
void fast_pow(vector<edge> st,vector<edge> a,int res,vector<edge> &I)
{
	I.clear();
	sort(st.begin(),st.end(),cmpx);
//	pout(st); 
	for(int i=1;i<=n+1;i++) I.push_back(edge{i,i,1});
	int cnt=0; 
	while(res)
	{
		if(res&1)  mult(st,I,I);
		mult(st,st,st);
		res>>=1;
		cnt++;
	}
//	cout << cnt << endl;
	mult(I,a,I);
}
int deg[N];
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++) ma.push_back(edge{i,i,1});
	for(int i=1;i<=n+1;i++) ma.push_back(edge{i,n+1,1});
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >> x >> y;
		ma.push_back(edge{x,y,1});
		ma.push_back(edge{y,x,1});
		deg[x]++,deg[y]++;
	}
	deg[n+1]=-1;
	for(int i=1;i<=n+1;i++) ans.push_back(edge{i,1,deg[i]+2});
	cin >> t;
	if(t>1e6) return 0;
	fast_pow(ma,ans,t-1,ans);
	cout << ans[0].w << endl;
	return 0;
}