9661 - HH 去散步

HH 有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时 HH 又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 1），问长度为 t，从给定地点 A 走到给定地点 B 共有多少条符合条件的路径。

第一行：五个整数 N,M,t,A,B。其中 N 表示学校里的路口的个数，M 表示学校里的路的条数，t 表示 HH 想要散步的距离，A 表示散步的出发点，而 B 则表示散步的终点。

接下来 M 行，每行一组 A_i,B_i，表示从路口 A_i 到路口 B_i 有一条路。数据保证 A_i \neq B_i，但不保证任意两个路口之间至多只有一条路相连接。路口编号从 0 到 N-1。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模 45989。

一行，表示答案。

对于 30\% 的数据，N \le 4，M \le 10，t \le 10。

对于 100\% 的数据，N \le 50，M \le 60，t \le 2^{30}，0 \le A,B。

山东省选