159. Day 5 PE. Kukuri的冒險

0 Judge

Code: 0

本題狀態

統計

Kukuri的冒險

sprout

題目敘述

$Kukuri$為了打倒魔王吉利與勇者開心的展開冒險了！已知在世界上有$K$個不同的區域，進入一個區域就要接受該區域的挑戰，而該區域挑戰通關後就能選擇下一個能到達的區域，已知第$i$個區域的關難度為$i$，$Kukuri$通過一個關卡之後，只能選擇一個難度比當前關卡困難的關卡前進繼續挑戰，如果給你每個區域通關後可以到達區域的地圖，你能找出$Kukuri$從起點新手村到魔王的城堡有幾種不同的關卡挑戰路線？

輸入說明

測資一開始有兩個數字$K~M$，$K$表示世界上有幾個區域，$M$表示有幾個連接兩區域的道路。接下來有$M$行，每行有$2$個數字$a~b$，表示區域$a,b$之間有一條路徑可以到達。在接下來有兩個數字$s~t$，表示新手村的區域位置與魔王城堡的區域位置。

  • $0 \leq K,M \leq 10^5$
  • $1 \leq a,b,s,t \leq K$
  • $a\neq b$
  • $s\neq t$

輸出說明

請輸出一行，為有幾種可能的方法，取其除以$1000000009$的餘數。

範例輸入

6 6
1 3
3 6
1 2
2 3
3 4
4 6
1 6

範例輸出

4

提示

Tip:測資很大、DP。


Judge Setting

run-time limit: 20 ms
memory limit: 655360 byte
測資數量: 0