TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.2% (37/41)

Submission's AC Ratio

49.1% (78/159)

Tags

Description

你有打過 2006 NPSC 高中組決賽 prob F. 假日的奇想曲 嗎?

馬可波羅(Marco Polo,又譯馬可孛羅馬哥波羅馬哥勃囉,1254年9月15日-1324年1月8日)是義大利威尼斯商人、旅行家、探險家。

1271年,馬可波羅的父親帶著兒子馬可,從威尼斯準備返回中國大都。由於戰爭不斷,馬可的父親有一張分析過的地圖。此時,聰明的馬可發現有好多條路可以通到大都!科科⋯⋯

於是,馬可向現在的你求救,總共有幾種走法呀?

聰明的馬可曉得,從 AB 必須越走越靠近大都,所以不會從 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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10