#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1000010, M = 110, P = 2017;

int n, m, t, x, y;
int f[35], g[35];
vector<int> e[M];
ll ans = 1;

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	scanf("%d", &t); 
	f[1] = 1;
	for (int i = 0; i < e[1].size(); i++)
		f[e[1][i]] = 1;
	for (int i = 1; i < t; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			ans = (ans + f[j]) % P;
			g[j] = (g[j] + f[j]) % P;
			for (int l = 0; l < e[j].size(); l++)
			{
				g[e[j][l]] = (g[e[j][l]] + f[j]) % P;
			}
		}
		swap(f, g);
	}

	for (int i = 1; i <= n; i++)
		ans = (ans + f[i]) % P;

	printf("%lld\n", ans);

	return 0;
}