/*By DennyQi 2018*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 10010; const int MAXM = 20010; const int INF = 1061109567; inline int Max(const int a, const int b){ return (a > b) ? a : b; } inline int Min(const int a, const int b){ return (a < b) ? a : b; } inline int read(){ int x = 0; int w = 1; register char c = getchar(); for(; c ^ '-' && (c < '0' || c > '9'); c = getchar()); if(c == '-') w = -1, c = getchar(); for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w; } int N,M,x,y,t; int a[35][35],g[100][100],ans[100][100],b[100][100]; inline void Matrix_ksm(int y){ while(y > 0){ if(y & 1){ for(int i = 1; i <= 2*N; ++i){ for(int j = 1; j <= 2*N; ++j){ b[i][j] = 0; for(int k = 1; k <= 2*N; ++k){ b[i][j] = (b[i][j] + ans[i][k] * g[k][j]) % 2017; } } } for(int i = 1; i <= 2*N; ++i){ for(int j = 1; j <= 2*N; ++j){ ans[i][j] = b[i][j]; } } } y /= 2; for(int i = 1; i <= 2*N; ++i){ for(int j = 1; j <= 2*N; ++j){ b[i][j] = 0; for(int k = 1; k <= 2*N; ++k){ b[i][j] = (b[i][j] + g[i][k] * g[k][j]) % 2017; } } } for(int i = 1; i <= 2*N; ++i){ for(int j = 1; j <= 2*N; ++j){ g[i][j] = b[i][j]; } } } } int main(){ // freopen(".in","r",stdin); N = read(), M = read(); for(int i = 1; i <= M; ++i){ x = read(), y = read(); a[x][y] = 1; a[y][x] = 1; } t = read(); for(int i = 1; i <= N; ++i){ a[i][i] = 1; } for(int i = 1; i <= N; ++i){ for(int j = 1; j <= N; ++j){ g[i][j] = a[i][j]; g[i][j+N] = a[i][j]; } } for(int i = N+1; i <= 2*N; ++i){ g[i][i] = 1; } for(int i = 1; i <= 2*N; ++i){ ans[i][i] = 1; } Matrix_ksm(t); int Ans = 1; for(int i = N+1; i <= N*2; ++i){ Ans = (Ans + ans[1][i]) % 2017; } printf("%d", Ans); return 0; }