思路
如果没有不能走上一条边的限制，很显然就是dp。
设f[i][j]表示到达i点走了j步的方案数，移到k点可以表示为f[k][j+1]+=f[i][j]。
如果有限制的话，可以考虑用边表示将之前思路中的i变为边的终点，只要不走同一条边，转移还是相同的。
但是t ≤ 2^30，显然直接dp是不可行的，这是机智的题解就想到了矩阵优化。
由于递推关系是线性的，可以搞一个行矩阵表示对于当前移动步数各个边的方案数。
转移可以考虑构造另一个矩阵，所有可以更新的边之间都变为1，其他是0，对于每一次转移都是一样的，所以只要将矩阵跑t次就可以了。
对于初始矩阵，可以加一条边设一个不存在的点，将它与起点相连，也方便之后的领接表。
此题疯狂卡时，辣鸡出题人。（据说多交几次就可以过
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int mod=;
int n,m,t,e,s,cnt,hd[],sum;
struct edge
{
int to,from,nxt;
}v[];
struct mat
{
int a[][];
mat()
{
memset(a,,sizeof(a));
}
mat operator * (mat x)
{
mat ans;
for(int i=;i<=cnt;i++)
for(int j=;j<=cnt;j++)
for(int k=;k<=cnt;k++)
ans.a[i][j]=(ans.a[i][j]+a[i][k]*x.a[k][j])%mod;
return ans;
}
}c,ans;
void addedge(int x,int y)
{
v[++cnt].nxt=hd[x];
v[cnt].from=x;
v[cnt].to=y;
hd[x]=cnt;
}
mat mul(mat x,int k)
{
mat res;
for(int i=;i<=cnt;i++)
res.a[i][i]=;
for(int i=k;i;i>>=,x=x*x)
if(i&)
res=res*x;
return res;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&t,&s,&e);
s++,e++;
addedge(,s);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
addedge(x,y),addedge(y,x);
}
for(int i=;i<=cnt;i++)
for(int j=;j<=cnt;j++)
if((i^j)!=&&v[i].to==v[j].from)
c.a[i][j]=;
ans.a[][]=;
c=mul(c,t);
ans=ans*c;
for(int i=;i<=cnt;i++)
if(v[i].to==e)
sum=(sum+ans.a[][i])%mod;
printf("%d\n",sum);
return ;
}