C++ :

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
    char c=nc();int len=0;
    for(;!((c>='A' && c<='Z')||(c>='a' && c<='z'));c=nc()) if (c==EOF) return 0;
    for(;((c>='A' && c<='Z')||(c>='a' && c<='z'));s[len++]=c,c=nc());
    s[len++]='\0';
    return len;
}

inline void read(char &x){
  for (x=nc();!(x=='?' || x=='+' || x=='-');x=nc());
}

int wt,ss[19];
inline void print(int x){
    if (x<0) x=-x,putchar('-'); 
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,m,T,f[40],g[40];
const int mo=2017;
struct data
{
    int f[40][40];
}a,b;

void add(data &x,data y)
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            x.f[i][j]=(x.f[i][j]+y.f[i][j])%mo;
}

void mul(data &x,data y)
{
    data z;
    memset(z.f,0,sizeof(z.f));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
                z.f[i][j]=((x.f[i][k]*y.f[k][j])%mo+z.f[i][j])%mo;
    x=z;
}

data Power(data x,int y)
{
    data res;
    memset(res.f,0,sizeof(res.f));
    for (int i=1;i<=n;i++)
        res.f[i][i]=1;
    for (;y;y>>=1)
    {
        if (y&1) mul(res,x);
        mul(x,x);
    }
    return res;
}

data Sum(data x,int y)
{
    data res;
    memset(res.f,0,sizeof(res.f));
    if (y==0) return res;
    if (y==1) return x;
    for (int i=1;i<=n;i++)
        res.f[i][i]=1;
    add(res,Power(x,y>>1));mul(res,Sum(x,y>>1));
    if (y&1) add(res,Power(x,y));
    return res;
}

int main()
{
    read(n);read(m);
    int x,y;
    memset(a.f,0,sizeof(a.f));
    for (int i=1;i<=m;i++)
        read(x),read(y),a.f[x][y]=1,a.f[y][x]=1;
    for (int i=1;i<=n;i++)
        a.f[i][i]=1;
    read(T);
    b=a;
    a=Power(a,T);
    memset(g,0,sizeof(g));
    memset(f,0,sizeof(f));
    g[1]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            f[i]=((g[j]*a.f[i][j])%mo+f[i])%mo;
    int ans=0;
    for (int i=1;i<=n;i++)
        ans=(ans+f[i])%mo;
    b=Sum(b,T-1);
    for(int i=1;i<=n;i++)
        b.f[i][i]=(b.f[i][i]+1)%mo; 
    memset(g,0,sizeof(g));
    memset(f,0,sizeof(f));
    g[1]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            f[i]=((g[j]*b.f[i][j])%mo+f[i])%mo;
    for (int i=1;i<=n;i++)
        ans=(ans+f[i])%mo;
    print(ans),puts("");
    return 0;
}