#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
#define pii pair<int,int>
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int mod=2017;

vector<vector<int>>multi(vector<vector<int>>& a,vector<vector<int>>&b)
{
    assert(a[0].size()==b.size());
    int n=a.size(),m=b.size(),k=b[0].size();
    vector<vector<int>>ret(n,vector<int>(k,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<k;j++)
        {
            for(int l=0;l<m;l++)
            {
                ret[i][j]+=a[i][l]*b[l][j];
                ret[i][j]=(ret[i][j]%mod+mod)%mod;
                //ret[j][l]=min(ret[j][l],a[j][i]+b[i][l]);

            }
        }
    }
    return ret;
}
vector<vector<int>> qpow(vector<vector<int>>a,int k)
{
    vector<vector<int>>ret=a;
    for(int i=0;(k>>i);i++)
    {
        if((k>>i)&1){ret=multi(ret,a);}
        a=multi(a,a);
    }
    return ret;
}
void solve()
{
  int n,m;cin>>n>>m;
  vector<vector<int>>arr(n+1,vector<int>(n+1));
  for(int i=1;i<=m;i++)
  {
    int a,b;cin>>a>>b;
    arr[a][b]=arr[b][a]=1;
  }
  for(int i=0;i<=n;i++)
  {
    arr[i][0]=1;
    arr[i][i]=1;
  }
  vector<vector<int>>ori(1,vector<int>(n+1));
  ori[0][1]=1;
  int t;cin>>t;
  arr=qpow(arr,t-1);
  arr=multi(ori,arr);
  int ans=0;
  for(int i=0;i<arr[0].size();i++)ans+=arr[0][i];
  ans%=mod;
  cout<<ans<<endl;
   
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}