#include<bits/stdc++.h>
#define pb push_back
using namespace std;
char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
inline int read(){
    int aa;
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';
    return aa;
}
const int mod=1315105,MAXM=1e9;
void add(int &x,const int y){if((x+=y)>=mod)x-=mod;}
void sub(int &x,const int y){if((x+=(mod-y))>=mod)x-=mod;}
int g[20000005],*ff=g,*f[5000005];
int n,m,k,seed,a[5000500],hd[5000005],nxt[10000005],to[10000005],tt=1;
void ADD(int u,int v){
	nxt[++tt]=hd[u],hd[u]=tt,to[tt]=v;
	nxt[++tt]=hd[v],hd[v]=tt,to[tt]=u;
}
int dfn[5000005],low[5000005],col,tot,stk[5000005],tail;
vector<int>road[10000005];
void tarjan(int u,int from){
	dfn[u]=low[u]=++tot,stk[++tail]=u;
	for(int i=hd[u],v;i;i=nxt[i]){
		v=to[i];if((i^1)==from)continue;
		if(!dfn[v]){
			tarjan(v,i),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				++col;road[col].pb(u),road[u].pb(col);
				while(1){
					int p=stk[tail--];
					road[col].pb(p),road[p].pb(col);
					if(p==v)break;
				}
			}
		}else low[u]=min(low[u],dfn[v]);
	}
}
const int inv2=(mod+1>>1);
int dep[10000005],len[5000005];
int up[5000005],son[5000005],vis[5000050];
vector<int>vec;
void dfs(int u){
    son[u]=-1,len[u]=0;
    for(int v:road[u]){
    	if(dep[v]<dep[u])continue;int id=-1;
    	for(int i=0;i<road[v].size();++i)if(road[v][i]==u){id=i;break;}
		vec.clear();
		for(int i=id;i<road[v].size();++i)vec.pb(road[v][i]);
		for(int i=0;i<id;++i)vec.pb(road[v][i]);
		road[v]=vec;int cir=vec.size();
		for(int i=1;i<road[v].size();++i)up[road[v][i]]=min(i,cir-i),dep[road[v][i]]=dep[u]+2;
		dep[v]=dep[u]+1;
		for(int i=1;i<road[v].size();++i){
			dfs(road[v][i]);
			if(son[u]==-1||len[u]<len[road[v][i]]+up[road[v][i]])len[u]=len[road[v][i]]+up[road[v][i]],son[u]=road[v][i];
		}
	}
	if(son[u]!=-1)vis[son[u]]=1;
}
int Ans;
int ct[20000005],bl[5000005];
void Add(int u,int p,int d){
	if(p==u||p==son[u])return;
	for(int i=0;i<=len[p];++i)add(ct[i+d],f[p][i]);
}
void Del(int u,int p,int d){
	if(p==u||p==son[u])return;
	for(int i=0;i<=len[p];++i)sub(ct[i+d],f[p][i]);
}
int p[10000005];
void solve(int u){
	f[u][0]=a[u];
    if(son[u]!=-1)f[son[u]]=f[u]+up[son[u]],solve(son[u]);
	for(int v:road[u]){
    	if(dep[v]<dep[u])continue;
		int fl=0;
    	for(int i=1;i<road[v].size();++i){
    		if(road[v][i]!=son[u])solve(road[v][i]);
    		else fl=1;
		}
		for(int i=1;i<road[v].size();++i)bl[road[v][i]]=i;
		int cir=road[v].size(),ans1=Ans;
		for(int i=0;i<road[v].size();++i)p[i+1]=p[i+cir+1]=road[v][i];
		int lef=(cir+1)/2;--lef;
		if(lef){
			int l=cir+1,r=cir;
			for(int i=cir+1;i<=2*cir;++i){
				if(p[i]==u||p[i]==son[u])continue;
				int ql=i-lef,qr=i-1;
				while(l>ql)--l,Add(u,p[l],2*cir-l);
				while(r<qr)++r,Add(u,p[r],2*cir-r);
				while(l<ql)Del(u,p[l],2*cir-l),++l;
				while(r>qr)Del(u,p[r],2*cir-r),--r;
				int d=-(2*cir-i);
				for(int j=0;j<=min(len[p[i]],k);++j){
					int d1=k-j-d;
					if(ct[d1])Ans=(Ans+1ll*ct[d1]*f[p[i]][j])%mod;
				}
			}
			while(l<=r)Del(u,p[l],2*cir-l),++l;
		}
		lef=cir-1-lef;
		for(int i=0;i<road[v].size();++i)p[i+1]=p[i+cir+1]=road[v][cir-1-i];
		if(lef){
			int l=cir+1,r=cir;
			for(int i=cir+1;i<=2*cir;++i){
				if(p[i]==u||p[i]==son[u])continue;
				int ql=i-lef,qr=i-1;
				while(l>ql)--l,Add(u,p[l],2*cir-l);
				while(r<qr)++r,Add(u,p[r],2*cir-r);
				while(l<ql)Del(u,p[l],2*cir-l),++l;
				while(r>qr)Del(u,p[r],2*cir-r),--r;
				int d=-(2*cir-i);
				for(int j=0;j<=min(len[p[i]],k);++j){
					int d1=k-j-d;
					if(ct[d1])Ans=(Ans+1ll*ct[d1]*f[p[i]][j])%mod;
				}
			}
			while(l<=r)Del(u,p[l],2*cir-l),++l;
		}
		sub(Ans,ans1);
		Ans=1ll*inv2*Ans%mod;
		add(Ans,ans1);
		for(int i=1;i<road[v].size();++i){
			int Id=road[v][i];if(Id==son[u])continue;
			for(int j=0;j<=min(len[Id],k-up[Id]);++j)if(k-up[Id]-j<=len[u]&&k-up[Id]-j)Ans=(Ans+1ll*f[u][k-up[Id]-j]*f[Id][j])%mod;
		}
		if(!fl){
			for(int i=1;i<road[v].size();++i){
				int Id=road[v][i];if(Id==son[u])continue;
				for(int j=0;j<=len[Id];++j)add(f[u][j+up[Id]],f[Id][j]);
			}
			continue;
		}
		for(int i=1;i<road[v].size();++i){
			int Id=road[v][i];if(Id==son[u])continue;
		    for(int j=0;j<=min(len[Id],k-up[Id]-up[son[u]]);++j)if(k-up[Id]-up[son[u]]-j<=len[son[u]])sub(Ans,1ll*f[son[u]][k-up[Id]-up[son[u]]-j]*f[Id][j]%mod);
			int d1=abs(bl[Id]-bl[son[u]]);d1=min(d1,cir-d1);
			for(int j=0;j<=min(len[Id],k-d1);++j)if(k-d1-j<=len[son[u]])Ans=(Ans+1ll*f[Id][j]*f[son[u]][k-d1-j])%mod;
		}
		for(int i=1;i<road[v].size();++i){
			int Id=road[v][i];if(Id==son[u])continue;
			for(int j=0;j<=len[Id];++j)add(f[u][j+up[Id]],f[Id][j]);
		}
	}
	if(k<=len[u])Ans=(Ans+1ll*f[u][k]*a[u])%mod;
}
int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;++i){
    	int u=read(),v=read();
        ADD(u,v);
	}
	seed=read();
	mt19937_64 rnd(seed);
        for(int i=1;i<=n;i++)a[i]=rnd()%MAXM+1,a[i]%=mod;
        return 0;
	col=n;
    tarjan(1,-1);if(n>4e6)return 0;
    for(int i=1;i<=col;++i)dep[i]=1e9;
    dep[1]=0;
	dfs(1);
    for(int i=1;i<=n;++i)if(!vis[i])f[i]=ff,ff+=(len[i]+1);

    solve(1);
	cout<<Ans<<endl;
	return 0;
}