1557 . 馬可波羅的奇想曲
TopCoder
Tags
Description
你有打過 2006 NPSC 高中組決賽 prob F. 假日的奇想曲 嗎？
馬可波羅（Marco Polo，又譯馬可孛羅、馬哥波羅、馬哥勃囉，1254年9月15日－1324年1月8日）是義大利威尼斯商人、旅行家、探險家。
1271年，馬可波羅的父親帶著兒子馬可，從威尼斯準備返回中國大都。由於戰爭不斷，馬可的父親有一張分析過的地圖。此時，聰明的馬可發現有好多條路可以通到大都！科科⋯⋯
於是，馬可向現在的你求救，總共有幾種走法呀？
聰明的馬可曉得，從 A 到 B 必須越走越靠近大都，所以不會從 B 走到 A 。如果到了終點，就不必再走下去囉！
我們保證起點到終點的路徑不會出現任何環。
Input Format
第一行是 $N$（$2 \le N \le 10000$），$M$（$1 \le M \le 100000$）表示有多少城市跟道路（包括海陸）。
接下來第二行到第 $M+1$ 行, 有 $A, B$ 兩個數, 表示 A 通向 B。
最後一行有 $V, D$ 表示威尼斯跟大都.
Output Format
假設從威尼斯到大都有 $R$ 種走法。
為了防止世界被破壞，為了保護世界的和平，只需輸出 $R \mod 1073741824 \ (2 ^ {30})$的走法.
如果沒有請輸出 $0$。（阿不然哩～？）
Sample Input 1
11 17
1 2
2 3
1 4
2 4
3 4
4 5
4 6
5 6
5 7
6 7
1 5
5 8
8 9
9 10
9 11
10 11
11 7
1 7
1 2
2 3
1 4
2 4
3 4
4 5
4 6
5 6
5 7
6 7
1 5
5 8
8 9
9 10
9 11
10 11
11 7
1 7
Sample Output 1
19
Hints
2010/7/9 更正錯字by DarkBtf
Problem Source
原TIOJ1557 / Problem Setter: 乃牛
2021.03.26 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |