렉시코폴리스

렉시코폴리스는 고대 전설과 보물로 알려진 도시이다. 이 도시는 복잡하게 얽힌 단방향 도로망으로 유명하다. 교차로는 $n$개이고 단방향 도로는 $m$개이다. 도로 $i$는 교차로 $u_i$에서 $v_i$로만 이동할 수 있게 하며, 마법의 수 $w_i$가 붙어 있다.

$s$에서 $t$까지 길이가 $k$인 경로는 도로의 나열 $e_1, e_2, \dots, e_k$이며, 이 순서대로 따라가면 $s$에서 $t$에 이를 수 있다. 두 경로를 비교할 때는 마법의 수가 처음으로 달라지는 위치를 본다. 그 위치에서 수가 작은 쪽이 사전순으로 더 작은 경로이다. 도로 번호가 아니라 마법의 수로 비교한다.

$s$에서 $t$까지 길이가 $k$인 경로 중 사전순으로 가장 작은 경로를 찾은 여행자는 정부에서 선물을 받는다는 소문이 있다. 이 경로를 찾는 프로그램을 작성하시오.

첫 줄에 여섯 정수 $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$로 나눈 나머지를 출력한다.

• $2 \le n \le 50$
• $1 \le m \le n^2 - n$
• $1 \le u_i, v_i \le n$이고 $u_i \ne v_i$이다.
• $1 \le w_i \le 10^9$
• 순서쌍 $(u_i, v_i)$는 서로 겹치지 않는다.
• $1 \le s, t \le n$
• $1 \le k \le 10^9$
• $1 \le x \le 10^9$