[SDOI2009]HH去散步

HH 有饭后散步的习惯。学校中的每条道路长度均为 $1$ ，他希望在一定时间内走过指定的距离。

散步时，HH 不会在下一步沿刚刚走过的同一条道路反向返回。不过，任意两个路口之间可能存在多条道路；如果 HH 通过其中一条道路到达另一端，再通过另一条平行道路返回，则不视为沿原路返回。

给定学校的地图、散步距离 $t$ 、起点 $A$ 和终点 $B$ ，请计算从 $A$ 出发、恰好走过长度 $t$ 后到达 $B$ ，且满足上述条件的散步路径数量。答案对 $45989$ 取模。

输入格式

第一行包含五个整数 $N$ 、 $M$ 、 $t$ 、 $A$ 、 $B$ ，分别表示学校中的路口数、道路数、散步距离、起点和终点。

接下来 $M$ 行，每行包含两个整数 $A_i$ 、 $B_i$ ，表示路口 $A_i$ 与路口 $B_i$ 之间有一条可双向通行的道路。

每一行描述一条独立的实体道路，任意两个路口之间可能存在多条道路。

同一行内的所有数据均由一个空格分隔，行首和行尾没有多余空格，输入中没有多余空行。

输出一行，包含一个整数，表示符合条件的路径数量对 $45989$ 取模后的结果。

本题为 SDOI 2009 试题「HH去散步」，题面与测试数据整理自 BZOJ。