说明

欢迎来到 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$ 行，每行包含三个整数 $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$ 是输入第一行给出的第五个数字。

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

提示

• $2 \le n \le 50$
• $1 \le m \le n^2 - n$
• $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 \ne v_i$，对于 $i \in \{1, 2, \dots, m\}$
• $(u_i, v_i) \ne (u_j, v_j)$，对于 $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$

翻译由 DeepSeek V3.2 完成