Fruit tea is a popular beverage. Making fruit tea requires mixing two ingredients. Let the weights of the two ingredients be $x$ and $y$; the "deliciousness" of the resulting fruit tea is $x \times y$. The market in SG City can be viewed as a cactus graph, where each node represents a stall, and each stall has one type of ingredient. Master Su discovered that ingredients from two stalls at a distance of $k$ are the most suitable for making fruit tea. He wants you to help him calculate the sum of the "deliciousness" of all possible fruit teas. The answer should be taken modulo $1315105$.

Brief problem statement: Calculate the sum of the products of weights for all pairs of nodes at distance $k$ in a cactus graph.

The distance between two stalls is the number of edges on the shortest path between them in the graph.

Input

The first line contains three integers $n, m, k$, representing the number of nodes, the number of edges, and the distance between nodes in the cactus graph, respectively.

The next $m$ lines each contain two integers $u, v$, representing an edge in the cactus graph.

The next line contains one integer $seed$. Participants should run the following code to obtain the weight $a_i$ for each node:

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

Output

Output a single integer representing the answer.

Examples

Input 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

Output 1

578532

Constraints

For all data, $1 \le n, m, k \le 5 \times 10^6$, $\forall i, 1 \le a_i \le 10^9$, $seed \le 10^9$.

Subtask 1 (10 points): $n, m, k \le 3500$.

Subtask 2 (10 points): $n, m, k \le 10^5$, $m = n - 1$.

Subtask 3 (10 points): $n, m, k \le 10^5$, $m = n$.

Subtask 4 (10 points): $n, m, k \le 10^5$, $m \le n + 20$.

Subtask 5 (20 points): $n, m, k \le 10^5$, the length of any cycle in the cactus is at most $20$.

Subtask 6 (20 points): $n, m, k \le 10^5$.

Subtask 7 (20 points): No special properties.

Special note: Due to the extremely large input size, it is recommended to use the provided fast I/O.

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