/** 题目：Lost in WHU 链接：https://oj.ejq.me/problem/26 题意:一个无向图，求从1出发到达n最多经过T条边的方法数，边可以重复经过，到达n之后不可以再离开。 思路：一个邻接矩阵（01矩阵）自身的T次方那么，a[i][j]的结果表示i到j经过T条边的方法数。（通过矩阵相乘理解 c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod; 表示i到j，通过i先到k，然后k到j；） 那么求a[1][n]的T步就是T个a矩阵相乘； 由于本题是T以内的方法数。那么通过对矩阵相乘的理解，可以想到增加一个n到达n的边。这时候保证T个矩阵相乘的过程中，当前已经获得的矩阵c 乘以一个a矩阵后，可以保证原先的c[1][n]方法数累加进去。即:c.m[1][n]*a.m[n][n]; 然后用快速幂加速矩阵相乘即可。 */ #include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 1e2+2; const int mod = 1e9+7; int n, m, k; struct mat { ll m[maxn][maxn]; mat operator*(const mat &b){ mat c, a = *this; memset(c.m, 0, sizeof c.m); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ for(int k = 1; k <= n; k++){ c.m[i][j] = (c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod; } } } return c; } mat operator^(int y){ mat x = *this; mat p; memset(p.m, 0, sizeof p.m); for(int i = 1; i <= n; i++){ p.m[i][i] = 1; } while(y>0){ if(y&1) p = p*x; x = x*x; y >>= 1; } return p; } } x; /* ll solve(int y) { mat p; memset(p.m, 0, sizeof p.m); for(int i = 1; i <= n; i++){ p.m[i][i] = 1; } while(y>0){ if(y&1) p = p*x; x = x*x; y >>= 1; } return p.m[1][n]; }*/ int main() { while(scanf("%d%d",&n,&m)!=EOF) { int u, v; memset(x.m, 0, sizeof x.m); for(int i = 0; i < m; i++){ scanf("%d%d",&u,&v); x.m[u][v] = x.m[v][u] = 1; } for(int i = 1; i < n; i++) x.m[n][i] = 0;///到达终点后不可以再出去，除非去自身。 x.m[n][n] = 1; scanf("%d",&k); //printf("%lld ",solve(k)); mat ans = x^k; printf("%lld ",ans.m[1][n]); } return 0; }