TopCoder

User's AC Ratio

95.0% (19/20)

Submission's AC Ratio

47.4% (27/57)

Tags

Description

有一天, Kiwigo 王國的 Skyly 心血來潮,

寫了個有高度智慧的病毒 ── 蚯蚓。

然因為 Skyly 只是寫好玩的,寫出蚯蚓後就一直晾著不用。

生氣的蚯蚓於是決定要闖出一番事業,讓 Skyly 看看自己的能力。

蚯蚓決定要在 OSSSC 1000 年入侵 Athena 並且把全部的資料都銷毀!

就在此時, Roy 找上了你,希望你能幫助他抵擋蚯蚓的入侵。

然而,要抵擋蚯蚓,必得先找出蚯蚓可能從那些地方入侵,

所以 Roy 希望你可以幫助它計算蚯蚓到底有幾種入侵的路徑!

強大的你是否有辦法幫助 Roy 抵抗蚯蚓病毒呢?

Input Format

第一行有三個數字 v e m ,代表有 v 個點 e 條線路。

接下來 e 行 每行有兩個數字 a b ,代表有一條從 a 到 b 的線路 (單向)

最後一行有兩個數字 s t ,代表蚯蚓在 s 而 Athena 在 t 。

0 < v ≦ 250, 0 < e ≦ 60000, 0 < m < 230

測資中保證不會有環。

Output Format

請輸出 從 s 到 t 有幾種連法。

而由於答案可能很大,所以請將答案 mod m。

Sample Input

4 5 100
0 1
0 2
1 2
2 3
1 3
0 3

Sample Output

3

Hints

OSSSC 是 Otis Skyly SmallSmallKuo Surwdkgo Calendar 之縮寫。

Problem Source

原TIOJ1589 / Problem Setter: coquelicot

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5