TopCoder

User's AC Ratio

85.7% (18/21)

Submission's AC Ratio

45.6% (36/79)

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

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 (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