Description
加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且
放在了加里敦星球的1号城市上。这个可乐机器人有三种行为：停在原地，去下一个相邻的
城市，自爆。它每一秒都会随机触发一种行为。现在给出加里敦星球城市图，在第0秒时可
乐机器人在1号城市，问经过了t秒，可乐机器人的行为方案数是多少？
Input
第一行输入两个正整数N,M表示城市个数，M表示道路个数。(1≤N≤30,0≤M≤100)
接下来M行输入u,v表示u,v之间有一条道路。
(1≤u,v≤n)保证两座城市之间只有一条路相连。
最后输入时间t。1<t≤10^6
Output
输出可乐机器人的行为方案数，答案可能很大，请输出对2017取模后的结果。
Sample Input
3 2
1 2
2 3
2
Sample Output
8
Solution
拿到这题一开始没什么头绪，然后一不小心手残点开了标签，然后就在正解的思路上奔腾。。。话说这题想不到真的挺。。。
我们考虑邻接矩阵的意义，假设一个邻接矩阵的边都是1，然后限定一个时间走1的长度，不难发现这个矩阵的k次幂就是走了k秒之后能到达每个点的路径数。
然后如果只能一直走的话就是计算出来即可。
那么它还可以停在原地，连一条自己到自己的边就可以了。
那么他还可以自爆。。。新建一个自爆点。。然后把每个点向这个点连一条有去无回的边，然后计算即可。
Code
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mo 2017
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
struct mul{
int k[35][35];
mul(){
memset(k,0,sizeof(k));
}
};
mul a;
int n,t,ans,m;
mul operator *(mul a,mul b){
mul q;
for(re int i=1;i<=n+1;i++)
for(re int j=1;j<=n+1;j++)
for(re int k=1;k<=n+1;k++)
q.k[i][j]=(q.k[i][j]+a.k[i][k]*b.k[k][j])%mo;
return q;
}
mul kasumi(mul a,int k){
mul rep;
for(re int i=1;i<=n;i++)
rep.k[i][i]=1;
while(k){
if(k&1) rep=rep*a;
a=a*a;
k>>=1;
}
return rep;
}
inline int read()
{
int x=0,c=1;
char ch=' ';
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
while(ch=='-') c*=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x*c;
}
int main()
{
n=read();m=read();
for(re int i=1;i<=m;i++){
int x=read(),y=read();
a.k[x][y]=a.k[y][x]=1;
}
t=read();
for(re int i=1;i<=n+1;i++)
a.k[i][i]=1,a.k[i][n+1]=1;
a=kasumi(a,t);
for(re int i=1;i<=n+1;i++)
ans=(ans+a.k[1][i])%mo;
cout<<ans;
return 0;
}