#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e7+5,M=(1<<22)+5,K=(1<<25)+5,mod=1315105,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));

namespace Rd{
	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;
	}
}

int n,m,k,A[N];
struct ljb{pair<int,int> f[N*2];int h[N],head;void add(int x,int y){f[++head]=make_pair(y,h[x]);h[x]=head;}}S,G;
int buf[N*4],*f[N*2],*F=buf;
void init(){
	int seed=Rd::read();
	mt19937_64 rnd(seed);
	int MAXM=1e9;
	for(int i=1;i<=n;i++) A[i]=rnd()%MAXM+1;
}
int Ct;
void con(int x,int y){G.add(x,y);}
namespace Tarjan{
	int dfn[N],low[N],dh,st[N],sh;
	void dfs(int x,int La){
		dfn[x]=low[x]=++dh;st[++sh]=x;
		for(int p=S.h[x],i=S.f[p].fi;p;p=S.f[p].se,i=S.f[p].fi) if(i^La){
			if(dfn[i]) {low[x]=min(low[x],dfn[i]);continue;}
			dfs(i,x);low[x]=min(low[x],low[i]);
			if(low[i]>=dfn[x]) {++Ct;con(x,Ct);while(st[sh+1]^i) con(Ct,st[sh--]);}
		}
	}
	void build(){
		Ct=n;dfs(1,0);
	}
}
int Le[N],son[N];
void dfs1(int x){
	for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) dfs1(i);
	if(x<=n){
		for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) Le[i]>Le[x]&&(son[x]=i,Le[x]=Le[i]);
	}else{
		int cir=1;
		for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) cir++;
		for(int p=G.h[x],i=G.f[p].fi,j=0;p;p=G.f[p].se,i=G.f[p].fi,j++) if(Le[i]+min(j+1,cir-j-1)>Le[x]) Le[x]=Le[i]+min(j+1,cir-j-1),son[x]=i;
	}
}
void dfs2(int x){
	f[x]=F;F+=Le[x]-Le[son[x]];if(!son[x]) F++;
	if(son[x]) dfs2(son[x]);
	for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) if(i^son[x]) dfs2(i);
}
ll ans;
int g[N*3];
void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
vector<int> scc;vector<pair<int,int> > clr;
void dfs3(int x){
	for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) dfs3(i);
	if(x<=n){
		// cerr<<x<<' '<<Le[x]<<' '<<son[x]<<'\n';
		if(k<=Le[x]) ans+=1ll*A[x]*f[x][k]%mod;
		f[x][0]=A[x]%mod;
		for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) if(i^son[x]){
			for(int j=0;j<=Le[i];j++) if(j+Le[x]>=k&&j<=k) ans+=1ll*f[i][j]*f[x][k-j]%mod;
			for(int j=0;j<=Le[i];j++) add(f[x][j],f[i][j]);
		}
	}else{
		scc.clear();
		for(int p=G.h[x],i=G.f[p].fi;p;p=G.f[p].se,i=G.f[p].fi) scc.emplace_back(i);
		int cir=scc.size()+1;
		int id=0;for(int i=0;i<scc.size();i++) if(scc[i]==son[x]) id=i;
		for(int i=0;i<scc.size();i++) if(scc[i]^son[x]){
			int y=scc[i],det=min(abs(i-id),cir-abs(i-id));
			for(int j=0;j<=Le[y];j++) if(j+det<=k&&j+det+Le[son[x]]>=k) ans+=1ll*f[y][j]*f[son[x]][k-det-j]%mod;
		}
		clr.clear();
		for(int i=0;i<cir/2;i++) {
			int y=scc[i];
			if(y^son[x]){
				for(int j=0;j<=Le[y];j++) add(g[j+i],f[y][j]);
				clr.emplace_back(i,i+Le[y]);
			} 
		}
		for(int i=0;i<scc.size();i++){
			int y=scc[i];
			if(y^son[x]) {
				for(int j=0;j<=Le[y];j++) add(g[j+i],mod-f[y][j]);
			}
			int pt=(i+cir/2)%cir;
			if(pt!=cir-1&&scc[pt]^son[x]){
				int z=scc[pt];
				for(int j=0;j<=Le[z];j++) add(g[j+i+cir/2],f[z][j]);
				clr.emplace_back(i+cir/2,i+cir/2+Le[z]);
			}
			if(y^son[x]){
				for(int j=0;j<=Le[y];j++) if(k-j+i>=0) ans+=1ll*g[k-j+i]*f[y][j]%mod;
			}
		}
		for(auto i:clr) fill(g+i.fi,g+i.se+1,0);
		if(cir%2==0){
			for(int i=0;i<scc.size();i++)if(scc[i]^son[x]&&i+cir/2<cir-1){
				int y=scc[i],z=scc[i+cir/2];if(z==son[x]) continue;
				int det=cir/2;//cerr<<Le[y]<<' '<<Le[z]<<' '<<det<<'\n';
				if(Le[y]<=Le[z]){
					for(int h=0;h<=Le[y];h++) if(h+det<=k&&h+det+Le[z]>=k) ans-=1ll*f[y][h]*f[z][k-det-h]%mod;
				}else{
					for(int h=0;h<=Le[z];h++) if(h+det<=k&&h+det+Le[y]>=k) ans-=1ll*f[z][h]*f[y][k-det-h]%mod;
				}
			}
		}
		for(int i=0;i<scc.size();i++) if(scc[i]^son[x]){
			int y=scc[i],det=min(i+1,cir-i-1);
			for(int j=0;j<=Le[y];j++) add(f[x][det+j],f[y][j]);
		}
	}
}
int main(){
	int i,j;n=Rd::read();m=Rd::read();k=Rd::read();
	while(m--){
		int x,y;x=Rd::read();y=Rd::read();
		S.add(x,y);S.add(y,x);
	}
	init();
	Tarjan::build();
	dfs1(1);
	dfs2(1);cerr<<"ZJAKIOI"<<' '<<Ct<<'\n';
	dfs3(1);
	printf("%lld\n",ans%mod);
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}