Description

Welcome to Lexicopolis, the ancient city of legends and treasures. The city is famous for its intricate network of one-way roads. There are $n$ intersections and $m$ one-way roads connecting the intersections. People can only travel from intersection $u_i$ to intersection $v_i$ along road $i$, and road $i$ is associated with a magical number $w_i$. A path of length $k$ from intersection $s$ to $t$ is a sequence of roads $e_1, e_2, \dots, e_k$ that allows travel from intersection $s$ to intersection $t$. A path is lexicographically smaller than another path if at the first road where they have different magic numbers (not index), the number on the first path is smaller than the number on the second path.

It is rumored that the tourist who figures out the lexicographically smallest path of length $k$ from intersection $s$ to intersection $t$ can receive a gift from the Lexicopolis government. Please write a program to find the lexicographically smallest path of length $k$ from intersection $s$ to $t$. If it is impossible to travel from intersection $s$ to $t$ with exactly $k$ roads, output $-1$.

Input Format

The first line contains six integers $n, m, s, t, x, k$. $n$ is the number of intersections. $m$ is the number of roads. $s$ is the starting intersection and $t$ is the ending intersection. $x$ is a number that will be used for outputting the answer. $k$ is the length of path. The $i$-th of the $m$ following lines contains three integers $u_i$, $v_i$ and $w_i$. That means road $i$ is from intersection $u_i$ to intersection $v_i$ and associated with magic number $w_i$.

Output Format

If there is no path of length $k$ from intersection $s$ to $t$, output -1. Otherwise, assume such a path exists. Consider the lexicographically smallest path $e_1, e_2, \dots, e_k$, and output $\sum_{i=1}^{k} w_{e_i} x^{k-i}$ modulo $10^9+7$, where $x$ is the number provided as the fifth value in the first line of the input.

3 6 1 3 10 4
1 2 2
2 1 1
1 3 1
3 1 2
2 3 1
3 2 2

1211

3 6 1 3 10 5
1 2 2
2 1 1
1 3 1
3 1 2
2 3 1
3 2 2

12121

6 7 5 6 10 10
1 2 1
2 4 2
3 4 1
4 5 3
5 3 5
4 6 2
6 5 1

121513477

6 7 1 6 123 2
1 2 1000000000
2 4 2
3 4 3
4 5 4
5 3 1
4 6 2
6 5 1

-1

Hint

• $2 \le n \le 50$
• $1 \le m \le n^2 - n$
• $1 \le u_i \le n$ for $i \in \{1, 2, \dots, m\}$
• $1 \le v_i \le n$ for $i \in \{1, 2, \dots, m\}$
• $1 \le w_i \le 10^9$ for $i \in \{1, 2, \dots, m\}$
• $u_i \ne v_i$ for $i \in \{1, 2, \dots, m\}$
• $(u_i, v_i) \ne (u_j, v_j)$ for $i \ne j$
• $1 \le s \le n$
• $1 \le t \le n$
• $1 \le k \le 10^9$
• $1 \le x \le 10^9$