Description

HH有個一成不變的習慣，喜歡飯后百步走。所謂百步走，就是散步，就是在一定的時間 內，走過一定的距離。 但是同時HH又是個喜歡變化的人，所以他不會立刻沿著剛剛走來的路走回。 又因為HH是個喜歡變化的人，所以他每天走過的路徑都不完全一樣，他想知道他究竟有多 少種散步的方法。 現在給你學校的地圖（假設每條路的長度都是一樣的都是1），問長度為t，從給定地 點A走到給定地點B共有多少條符合條件的路徑

Input

第一行：五個整數N，M，t，A，B。其中N表示學校里的路口的個數，M表示學校里的 路的條數，t表示HH想要散步的距離，A表示散步的出發點，而B則表示散步的終點。 接下來M行，每行一組Ai，Bi，表示從路口Ai到路口Bi有一條路。數據保證Ai = Bi，但 不保證任意兩個路口之間至多只有一條路相連接。 路口編號從0到N ? 1。 同一行內所有數據均由一個空格隔開，行首行尾沒有多余空格。沒有多余空行。 答案模45989。

Output

一行，表示答案。

Sample Input

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

Sample Output

4

HINT

對于30%的數據，N ≤ 4，M ≤ 10，t ≤ 10。 對于100%的數據，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Solution

這道題就是矩陣乘法，但是我們要把矩陣變一下。題目中要求不能立刻走回頭路，但是又有重邊，所以常規的鄰接矩陣是不行的。我們要用邊構矩陣。先把無向邊拆成兩條有向邊，然后得出矩陣A，其中Ai,j=1$A_{i,j}=1$表示i號邊可以到達j號邊。然后求出At?1$A^{t-1}$，此時A′i,j$A'_{i,j}$就表示從i號邊到j號邊走了t-1條邊的方案數。 然后我們枚舉每條起點的出邊i，對于每條出邊再枚舉每條終點的入邊j，∑A′i,j$/sum A'_{i,j}$就是答案。

代碼：