当前没有测试数据。

【例题3】行为方案

题目描述

加里顿星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里顿星球的$1$号城市上。这个可乐机器人有三种行为：停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给出加里顿星球城市图，在第$0$秒时可乐机器人在$1$号城市，问经过了$t$秒，可乐机器人的行为方案数是多少？

输入格式

第一行输入两个正整数$n$，$m$，$n$表示城市数，$m$表示道路数。

接下来$m$行输入$u$，$v$，表示$u$，$v$之间有一条双向道路。

最后输入时间$t$。

输出格式

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

数据范围与提示

对于$100\%$的数据，$1 \leq n,m \leq 100$，$1 \leq t \leq 10^{9}$。

样例

3 2
1 2
2 3
2

8