環狀線-1
發布時間: Sept. 30, 2024, 11:42 p.m. 最後更新時間: Oct. 20, 2024, 10:46 a.m. 時間限制: 3000ms 記憶體限制: 128M
西元3024年，A星球花費100年建造的環狀線超音速列車終於完工了！
已知此列車共停靠$n$個車站，編號為$1$~$n$
環狀線，顧名思義所有車站要圍成一個圈，因此第$i$號車站有可以開往第$i+1$號車站的單向道路（第$n$號車站則有可以開往第$1$號車站的單向道路）
但為了增加幾個大站間的通勤效率，當局額外建造了$m$條單向道路，每條分別連接兩個相異車站（任意兩車站之間同方向至多只有一條道路）
A星球的某位稽查員為了測試這條路網是否能夠安全運行，需要從第$s$號車站出發，連續經過$k$個車站（可以重複，不含起點），請問他一共有多少種搭乘路線可以選擇？
（數字可能很⼤，請將答案對$10^9+7$取餘）
第一行輸入三正整數$n,m,k$，$2\le n\le 10^2$，$0\le m\le P(n,2)-n$，$1\le k\le 10^{18}$
接下來$m$行每行輸入兩正整數$a,b$，表示有一條額外道路由第$a$號車站通往第$b$號車站
最後一行輸入一正整數$s$，表示某位稽查員的起始站
輸出一正整數$ans$，表示某位稽查員一共有多少種搭乘路線可以選擇
（數字可能很⼤，請將答案對$10^9+7$取餘）
複製範例
6 3 7 1 3 2 4 2 6 3
4
複製範例
4 2 6 1 3 4 2 2
5
