環狀線-2
發布時間: Sept. 30, 2024, 11:54 p.m. 最後更新時間: Oct. 1, 2024, 1:42 a.m. 時間限制: 5000ms 記憶體限制: 128M
西元3034年，由於科技日益發達，A星球只花費10年就完成環狀線超音速列車的擴建！但考量到之前路分支道路的載客率不高，因此當局決定減少額外建造的道路數量。
（本題僅有參數範圍與環狀線-1不同）
已知此列車共停靠$n$個車站，編號為$1$~$n$
環狀線，顧名思義所有車站要圍成一個圈，因此第$i$號車站有可以開往第$i+1$號車站的單向道路（第$n$號車站則有可以開往第$1$號車站的單向道路）
但為了增加幾個大站間的通勤效率，當局額外建造了$m$條單向道路，每條分別連接兩個相異車站（任意兩車站之間同方向至多只有一條道路）
A星球的某位稽查員為了測試這條路網是否能夠安全運行，需要從第$s$號車站出發，連續經過$k$個車站（可以重複，不含起點），請問他一共有多少種搭乘路線可以選擇？
（數字可能很⼤，請將答案對$10^9+7$取餘）
第一行輸入三正整數$n,m,k$，$2\le n\le 10^6$，$0\le m\le 100$，$1\le k\le 10^{5}$
接下來$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
