欢迎来到 Lexicopolis，一座充满传说与宝藏的古老城市。这座城市以其错综复杂的单向道路网络而闻名。城市中共有 $n$ 个路口和 $m$ 条连接这些路口的单向道路。人们只能沿着道路 $i$ 从路口 $u_i$ 前往路口 $v_i$，且每条道路 $i$ 都关联着一个魔法数字 $w_i$。一条从路口 $s$ 到 $t$ 的长度为 $k$ 的路径是指一个道路序列 $e_1, e_2, \dots, e_k$，它使得人们可以从路口 $s$ 旅行到路口 $t$。如果两条路径在它们具有不同魔法数字（而非道路编号）的第一条道路上，第一条路径上的数字小于第二条路径上的数字，则称第一条路径的字典序小于第二条路径。

传闻，能够找出从路口 $s$ 到路口 $t$ 的长度为 $k$ 的字典序最小路径的游客，将获得来自 Lexicopolis 政府的礼物。请编写一个程序，寻找从路口 $s$ 到 $t$ 的长度为 $k$ 的字典序最小路径。如果无法通过恰好 $k$ 条道路从路口 $s$ 旅行到 $t$，则输出 -1。

输入格式

第一行包含六个整数 $n, m, s, t, x, k$。$n$ 是路口的数量。$m$ 是道路的数量。$s$ 是起点路口，$t$ 是终点路口。$x$ 是一个用于输出答案的数字。$k$ 是路径的长度。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$。这表示道路 $i$ 从路口 $u_i$ 连向路口 $v_i$，且关联的魔法数字为 $w_i$。

输出格式

如果不存在从路口 $s$ 到 $t$ 的长度为 $k$ 的路径，输出 -1。否则，假设存在这样一条路径。设字典序最小的路径为 $e_1, e_2, \dots, e_k$，输出 $\sum_{i=1}^{k} w_{e_i} x^{k-i}$ 对 $10^9+7$ 取模后的结果，其中 $x$ 是输入第一行中提供的第五个数值。

数据范围

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

样例

输入样例 1

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

输出样例 1

1211

输入样例 2

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

输出样例 2

12121

输入样例 3

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

输出样例 3

121513477

输入样例 4

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

输出样例 4

-1