TopCoder

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

54.5% (18/33)

Description

建中國有 N 座城市,其中有一些道路可以作為聯絡兩座城市之用。

對於每一個城市,為了方便起見,我們將他們依序編號成 1 到 N 的正整數;

而對於每一條聯絡道路,都是「雙向」的且恰好可以聯絡兩座城市 Ai 和 Bi

意即可以利用該條道路從城市 Ai 到達城市 Bi,也可以從城市 Bi 經由這條道路到達城市 Ai

由於在這個國家的城市之間充斥著許多聯絡道路,因此喜歡思考的曉涵就產生了一個疑問:

「如果我要從城市 S 前往城市 T,並且規定恰好要走過 K 條聯絡道路的話,有幾種走法呢?」(同一條連絡道路走過 n 次視為走過 n 條道路)

為了簡化題目,我們可以忽略城市內的交通網路,你可以將每個城市當作一個中繼站,

一旦進去馬上出來且城市內複雜的子道路將不應該被計算在經過的道路數中(其實你也不會知道 :P )。

此外,在經過 K 條路後恰好到達終點城市 T 之前經過城市 T 是被允許的,這種可能也應該被計算進去。

最後,一條邊可以重複走很多次不會毀損或壞掉。

Input Format

對於每一筆測試資料,第一行有五個整數 N、M、S、T、K,之後有 M 行,
2≤N≤100, 0≤M≤50000, 0≤K≤1015
每一行有兩個整數 Ai、Bi,代表每一條道路所連接的城市編號。

Output Format

請輸出一個整數 R,代表從起點到終點且符合條件的走法數 (路徑數) 除以1000000009 的餘數

Sample Input

Sample Input 1:
3 2 1 3 2
1 2
2 3

Sample Input 2:
4 3 1 3 3
1 2
2 3
1 4

Sample Output

Sample Output 1:
1

Sample Output 2:
0

Hints

Problem Source

原TIOJ1778 / 99建中校內資訊能力競賽(prob3)

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) Output Limit (KiB)
0 2000 131072 262144
1 2000 131072 262144
2 2000 131072 262144
3 2000 131072 262144
4 2000 131072 262144
5 2000 131072 262144
6 2000 131072 262144
7 2000 131072 262144
8 2000 131072 262144
9 2000 131072 262144