水果茶是一种广受好评的饮料。制作水果茶需要将两种原料混合。设两种原料的权值分别为 $ x,y $，则制成的水果茶的“美味度”为 $ x\times y $。SG 城的市场可以看做一张仙人掌图，每个点代表一个摊位，每个摊位上有一种原料。苏师傅发现距离为 $ k $ 的两个摊位的原料最适合制作水果茶。他想让你帮他求出制作所有可能的水果茶的“美味度”之和。答案对 $ 1315105 $ 取模。

简要题意：求仙人掌图上所有距离为 $ k $ 的点对的权值积的和。

两个摊位的距离指他们在图上的最短路径经过的边数。

输入格式

第一行三个整数 $ n,m,k $，分别表示仙人掌的点数、边数与点对间的距离。

接下来 $ m $ 行每行两个整数 $ u,v $ 表示仙人掌的一条边。

接下来一行 $ 1 $ 个整数 $ seed $，选手根据 $ seed $ 运行如下代码得到每个点的权值 $ a_i $。

mt19937_64 rnd(seed);
int MAXM=1e9;
for(int i=1;i<=n;i++)a[i]=rnd()%MAXM+1;

输出格式

输出一行一个整数表示答案。

样例

样例输入

12 14 4
1 2
2 3
1 4
4 5
3 5
5 6
6 7
5 7
7 8
8 9
9 10
7 10
3 11
11 12
27455

样例输出

578532

数据规模与约定

对于所有数据，$ 1\le n,m,k\le 5\times 10^6 $，$ \forall i,1\le a_i\le 10^9 $，$ seed\le 10^9 $。

子任务 1（10 分）：$ n,m,k\le 3500 $。

子任务 2（10 分）：$ n,m,k\le 10^5 $，$ m=n-1 $。

子任务 3（10 分）：$ n,m,k\le 10^5 $，$ m=n $。

子任务 4（10 分）：$ n,m,k\le 10^5 $，$ m\le n+20 $。

子任务 5（20 分）：$ n,m,k\le 10^5 $，保证仙人掌的环长不超过 $ 20 $。

子任务 6（20 分）：$ n,m,k\le 10^5 $。

子任务 7（20 分）：无特殊性质。

特别提醒：由于本题输入量极大，建议使用下发快读。

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;
}