#include<bits/stdc++.h>
using std::cin,std::cout;
const int P=2017;
int n,m,t;
struct Mat{
  int a[31][31];
  Mat operator*(Mat b){
    Mat res;
    for(int i=0;i<=n;++i)
      for(int j=0;j<=n;++j)
        for(int k=0;k<=n;++k)
          (res.a[i][j]+=a[i][k]*b.a[k][j])%=P;
    return res;
  }
} now;
Mat qpow(int b){
  Mat res;
  memset(&res,0,sizeof res);
  for(int i=0;i<=n;++i) res.a[i][i]=1;
  for(;b;b>>=1,now=now*now)
    if(b&1) res=res*now;
  return res;
}
main(){
  cin>>n>>m;
  for(int u,v;m--;){
    cin>>u>>v;
    now.a[u][v]=now.a[v][u]=1;
  }
  for(int i=0;i<=n;++i) now.a[i][i]=1;
  for(int i=1;i<=n;++i) now.a[i][0]=1; 
  cin>>t;
  Mat now=qpow(t);
  int res=0;
  for(int i=0;i<=n;++i) res+=now.a[1][i];
  cout<<(res%P)<<'\n';
}