0 Judge
Code: 0
$Kukuri$為了打倒魔王吉利與勇者開心的展開冒險了!已知在世界上有$K$個不同的區域,進入一個區域就要接受該區域的挑戰,而該區域挑戰通關後就能選擇下一個能到達的區域,已知第$i$個區域的關難度為$i$,$Kukuri$通過一個關卡之後,只能選擇一個難度比當前關卡困難的關卡前進繼續挑戰,如果給你每個區域通關後可以到達區域的地圖,你能找出$Kukuri$從起點新手村到魔王的城堡有幾種不同的關卡挑戰路線?
測資一開始有兩個數字$K~M$,$K$表示世界上有幾個區域,$M$表示有幾個連接兩區域的道路。接下來有$M$行,每行有$2$個數字$a~b$,表示區域$a,b$之間有一條路徑可以到達。在接下來有兩個數字$s~t$,表示新手村的區域位置與魔王城堡的區域位置。
請輸出一行,為有幾種可能的方法,取其除以$1000000009$的餘數。
6 6
1 3
3 6
1 2
2 3
3 4
4 6
1 6
4
Tip:測資很大、
。