可乐（数据加强版）

• 时间限制：1 秒
• 内存限制：128 MiB

题目背景

原题 P3758 的数据较弱。这个加强版会卡掉暴力动态规划做法，并补充原题题面中缺少的公式排版。

题目描述

加里敦星球的人们特别喜欢喝可乐，因此他们的敌对星球研发了一个可乐机器人，并把它放在加里敦星球的 $1$ 号城市。

可乐机器人有三种行为：停在原地、前往一个相邻城市、自爆。它每秒都会触发一种行为。如果机器人选择自爆，该方案立即终止；否则它会继续下一秒的行为。第 $0$ 秒时还没有触发任何行为，因此当 $t=0$ 时，空行为序列也计为一种方案。

给定加里敦星球的城市图。在第 $0$ 秒时，可乐机器人位于 $1$ 号城市。求经过 $t$ 秒时，可乐机器人的行为方案数。

输入格式

第一行包含两个正整数 $N,M$，分别表示城市数量和道路数量。

接下来 $M$ 行，每行包含两个整数 $u,v$，表示城市 $u$ 与城市 $v$ 之间有一条双向道路。图中没有自环或重边，图不保证连通。

最后一行包含一个整数 $t$，表示时间。

输出格式

输出可乐机器人的行为方案数。答案可能很大，请输出其对 $2017$ 取模后的结果。

样例输入 1

3 2
1 2
2 3
2

样例输出 1

8

样例解释

共有以下 $8$ 种方案：

• $1 \rightarrow$ 爆炸；
• $1 \rightarrow 1 \rightarrow$ 爆炸；
• $1 \rightarrow 2 \rightarrow$ 爆炸；
• $1 \rightarrow 1 \rightarrow 1$；
• $1 \rightarrow 1 \rightarrow 2$；
• $1 \rightarrow 2 \rightarrow 1$；
• $1 \rightarrow 2 \rightarrow 2$；
• $1 \rightarrow 2 \rightarrow 3$。

数据范围

对于所有数据，$2\le N\le100$，$1\le M\le100$，$0\le t\le10^9$，$1\le u,v\le N$。