TopCoder

Thumb 49067563 587284918383704 8873838024824193024 n
$Yojahuang$
你只會寫水題嗚嗚嗚

User's AC Ratio

85.0% (17/20)

Submission's AC Ratio

44.7% (34/76)

Tags

Description

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

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

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

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

聰明的馬可曉得,從A到B必須越走越靠近大都,所以不會從B走到A。如果到了終點,就不必再走下去囉!

我們保證起點到終點的路徑不會出現任何環。

Input Format

第一行是N(2<=N<=10000), M(1<=M<=100000) 表示有多少城市跟道路(包括海陸).

接下來第二行到第 E+1 行, 有 A B 兩個數, 表示A通向B

最後一行有V, D 表示威尼斯大都.

Output Format

假設從威尼斯到大都有R種走法.

為了防止世界被破壞, 為了保護世界的和平, 只需輸出R mod 1073741824 (230 )的走法.

如果沒有請輸出 0. (阿不然哩~?)

Sample Input

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

19

Hints

2010/7/9 更正錯字by DarkBtf

Problem Source

原TIOJ1557 / Problem Setter: 乃牛

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536