#include <cstdio>
#include <random>
#include <cstring>
#include <algorithm>
#pragma GCC optimize(2,3,"Ofast")
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin)),p1==p2?EOF:*p1++)
using namespace std;
char buf[1<<22],*p1=buf,*p2=buf;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=5000003,P=1315105;
const int MAXM=1e9;
const int M=10000003;
typedef long long ll;
int n,m,k;
int w[N],res;
int *nd[N],len[N],cnt;
inline void inc(int &x,int v){if((x+=v)>=P) x-=P;}
inline void dec(int &x,int v){if((x-=v)<0) x+=P;}
namespace BCT{
	int hd[M],ver[M<<1],nxt[M<<1],tot;
	inline void add(int u,int v){
		nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;
		nxt[++tot]=hd[v];hd[v]=tot;ver[tot]=u;
	}
	int mx[M],sn[M];
	void dfs(int u,int fa){
		if(u>n){
			int p=u-n;
			rotate(nd[p],find(nd[p],nd[p]+len[p],fa),nd[p]+len[p]);
			for(int i=1;i<len[p];++i){
				int v=nd[p][i];
				dfs(v,u);
				int d=mx[v]+min(len[p]-i,i);
				if(d>mx[u]) mx[u]=d,sn[u]=v;
			}
		}
		else{
			for(int i=hd[u];i;i=nxt[i]){
				int v=ver[i];
				if(v==fa) continue;
				dfs(v,u);
				int d=mx[v]+(v<=n);
				if(d>mx[u]) mx[u]=d,sn[u]=v;
			}
		}
	}
	int *f[M];
	void alc(int u,int fa,bool tp){
		if(tp){
			f[u]=new int[mx[u]+1];
			memset(f[u],0,(mx[u]+1)<<2);
		}
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa) continue;
			if(v==sn[u]){
				f[v]=f[u]+mx[u]-mx[v];
				alc(v,u,0);
			}
			else alc(v,u,1);
		}
	}
	int arr[M<<1];
	void proc(int u,int fa){
		if(u>n){
			int p=u-n,sp=0,smx=0;
			for(int i=1;i<len[p];++i){
				proc(nd[p][i],u);
				if(nd[p][i]==sn[u]) sp=i;
			}
			int md=len[p]>>1;
			for(int i=1;i<len[p];++i){
				int v=nd[p][i];
				if(i!=sp){
					int ds=abs(sp-i);
					if(ds<=md){
						for(int t=max(0,k-ds-mx[sn[u]]);t<=mx[v]&&t+ds<=k;++t)
							res=(res+(ll)f[v][t]*f[sn[u]][k-ds-t])%P;
						ds=min(i,len[p]-i);
						for(int t=max(0,k-ds-mx[u]);t<=mx[v]&&t+ds<=k;++t)
							res=(res-(ll)f[v][t]*f[u][k-ds-t])%P;
					}
				}
			}
			for(int i=1;i<len[p];++i){
				if(i!=sp){
					int d=min(i,len[p]-i),v=nd[p][i];
					if(d+mx[v]>smx) smx=d+mx[v];
					for(int t=0;t<=mx[v]&&t+d<=k;++t) res=(res-(ll)f[v][t]*arr[k-d-t])%P;
					for(int t=0;t<=mx[v];++t) inc(arr[t+d],f[v][t]);
				}
				if(i>md&&i-md!=sp){
					int d=min(i-md,len[p]-i+md),v=nd[p][i-md];
					for(int t=0;t<=mx[v];++t) dec(arr[t+d],f[v][t]);
				}
			}
			for(int i=0;i<=smx;++i) arr[i]=0;
			for(int i=len[p]-1;i;--i){
				if(i!=sp){
					int v=nd[p][i];
					for(int t=0;t<=mx[v]&&t<=k+i;++t) res=(res+(ll)f[v][t]*arr[k+i-t])%P;
					for(int t=0;t<=mx[v];++t) inc(arr[t+i],f[v][t]);
				}
				if(i+md<len[p]&&i+md!=sp){
					int v=nd[p][i+md];
					for(int t=0;t<=mx[v];++t) dec(arr[t+i+md],f[v][t]);
				}
			}
			for(int i=0;i<=smx+len[p];++i) arr[i]=0;
			for(int i=1;i<len[p];++i)
				if(i!=sp){
					int d=min(i,len[p]-i),v=nd[p][i];
					for(int t=max(0,k-d-mx[u]);t<=mx[v]&&t+d<=k;++t) res=(res+(ll)f[v][t]*f[u][k-d-t])%P;
					for(int t=0;t<=mx[v];++t) inc(f[u][t+d],f[v][t]);
				}
		}
		else{
			for(int i=hd[u];i;i=nxt[i]){
				int v=ver[i];
				if(v==fa) continue;
				proc(v,u);
			}
			if(k<=mx[u]) res=(res+(ll)w[u]*f[u][k])%P;
			inc(f[u][0],w[u]);
			for(int i=hd[u];i;i=nxt[i]){
				int v=ver[i];
				if(v==fa) continue;
				int d=(v<=n);
				if(v!=sn[u]){
					for(int t=max(0,k-d-mx[u]);t<=mx[v]&&t+d<=k;++t)
						res=(res+(ll)f[v][t]*f[u][k-d-t])%P;
					for(int t=0;t<=mx[v];++t) inc(f[u][t+d],f[v][t]);
				}
			}
		}
	}
}
namespace GR{
	int hd[N],ver[N<<1],nxt[N<<1],tot=1;
	inline void add(int u,int v){nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;}
	int ft[N],de[N],fe[N];
	bool tr[N];
	void dfs(int u,int fa){
		de[u]=de[fa]+1;ft[u]=fa;
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa) continue;
			if(de[v]&&de[v]<de[u]){
				int clen=de[u]-de[v]+1;
				nd[++cnt]=new int[clen];
				len[cnt]=clen;
				for(int p=u;;p=ft[p]){
					BCT::add(nd[cnt][de[u]-de[p]]=p,cnt+n);
					if(p==v) break;
					tr[fe[p]]=0;
				}
			}
			else if(!de[v]) tr[fe[v]=i>>1]=1,dfs(v,u);
		}
	}
}
int eu[N],ev[N];
int main(){
	n=read();m=read();k=read();
	for(int i=1;i<=m;++i){
		eu[i]=read();ev[i]=read();
		GR::add(eu[i],ev[i]);GR::add(ev[i],eu[i]);
	}
	int seed=read();
	mt19937_64 rng(seed);
	for(int i=1;i<=n;++i) w[i]=(rng()%MAXM+1)%P;
	GR::dfs(1,0);
	for(int i=1;i<=m;++i) if(GR::tr[i]) BCT::add(eu[i],ev[i]);
	BCT::dfs(1,0);BCT::alc(1,0,1);BCT::proc(1,0);
	if(res<0) res+=P;
	printf("%d\n",res);
	return 0;
}