輸入第一行有五個整數 $N, M, S, T, K$，代表檢查站的數量、道路的數量、起點、終點，以及路線需要恰好跑過的道路段數。

接下來 $M$ 行，第 $i$ 行有兩個整數 $u_i, v_i$，代表第 $i$ 條道路連接檢查站 $u_i$ 與檢查站 $v_i$。

• $1 \leq N \leq 100$
• $0 \leq M \leq \min(100, \frac{N(N-1)}{2})$
• $1 \leq S, T \leq N$
• $1 \leq K \leq 10^ {18}$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• 任兩個檢查站之間最多只有一條道路（沒有重邊，也沒有自環）。

輸出一行一個整數，代表恰好跑完 $K$ 段道路後停在檢查站 $T$ 的機率。

這個機率一定可以寫成一個最簡分數 $\dfrac{p}{q}$，其中 $p, q$ 為非負整數、$q > 0$ 且 $q$ 與 $10^ 9+7$ 互質。由於機率通常不是整數，無法直接輸出分數，因此請改為輸出 $p \times q^ {-1} \bmod (10^ 9+7)$，其中 $q^ {-1}$ 是 $q$ 在模 $10^ 9+7$ 下的模逆元——也就是唯一滿足 $q \times q^ {-1} \equiv 1 \pmod{10^ 9+7}$ 的整數。

換句話說，請輸出唯一一個整數 $x$，$0 \le x < 10^ 9+7$，使得

$$x \times q \equiv p \pmod{10^ 9+7}.$$

特別地，若不存在任何合法路線（機率為 $0$），此時 $p = 0$，直接輸出 $0$ 即可。

範測 1 解釋：

地圖上檢查站 $1,2,3,4$ 之間除了 $1-4$ 以外兩兩都有道路相連，度數分別是 $\deg(1)=2,\deg(2)=3,\deg(3)=3,\deg(4)=2$。從檢查站 $1$ 出發，跑完 $3$ 段道路後停在檢查站 $4$ 的所有路線與機率如下：

| 路線 | 每一步的選擇機率 | 這條路線的機率 |
| :---: | :---: | :---: |
| $1 \to 2 \to 3 \to 4$ | $\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2}$ | $\frac{1}{8}$ |
| $1 \to 3 \to 2 \to 4$ | $\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2}$ | $\frac{1}{8}$ |

（另外像 $1\to2\to4\to3$、$1\to3\to4\to2$ 這兩條路線雖然中途有經過檢查站 $4$，但跑完 $3$ 段道路時分別停在檢查站 $3$ 和檢查站 $2$，不算數。）

因此恰好跑完 $3$ 段道路、最後停在檢查站 $4$ 的機率為 $\frac{1}{8}+\frac{1}{8}=\frac{1}{4}$。將 $\frac{1}{4}$ 表示成 $p \times q^ {-1} \bmod (10^ 9+7)$ 的形式，即 $p=1,q=4$，答案為 $1 \times 4^ {-1} \bmod (10^ 9+7) = 250000002$。

範測 2 解釋：

地圖是鏈狀 $1 - 2 - 3$，其中 $\deg(1)=1,\deg(2)=2,\deg(3)=1$。從檢查站 $1$ 出發，因為 $\deg(1)=1$，第一步只能（機率為 $1$）跑到檢查站 $2$；到了檢查站 $2$ 之後，因為不能馬上調頭跑回檢查站 $1$，唯一合法選項是跑到檢查站 $3$（機率為 $1$）；但到了檢查站 $3$ 之後，唯一相連的道路又是通往檢查站 $2$，跑回去會構成馬上調頭，不合法——此時已經沒有任何合法的下一步了。因此這趟訓練在跑完 $2$ 段道路後就必定失敗，不存在跑滿 $3$ 段道路的路線，機率為 $0$。

2026 YTP 高中組決賽 p9