我们知道，邻接矩阵自乘t次就是经过t条边的路径数
但这道题显然不能这样，因为不能走回头路
于是我们可以构造边的邻接矩阵矩乘即可
const mo=;
type way=record
po,fr:longint;
end;
node=array[..,..] of longint; var c,a,w:node;
ed:array[..] of way;
x,y,n,m,s,t,e,i,j,ans,len:longint; procedure add(x,y:longint);
begin
inc(len);
ed[len].po:=y;
ed[len].fr:=x;
end; procedure mul(var c:node;a,b:node);
var i,j,k:longint;
begin
for i:= to len do
for j:= to len do
begin
c[i,j]:=;
for k:= to len do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod mo;
end;
end; procedure quick(n:longint);
begin
while n> do
begin
if n mod = then mul(a,a,w);
mul(w,w,w);
n:=n shr ;
end;
end; begin
len:=;
readln(n,m,t,s,e);
inc(s);
inc(e);
for i:= to m do
begin
readln(x,y);
inc(x); inc(y);
add(x,y);
add(y,x);
end;
for i:= to len do
begin
for j:= to len do
if (i xor <>j) then
if ed[i].po=ed[j].fr then w[i,j]:=;
a[i,i]:=;
if ed[i].fr=s then c[,i]:=;
end;
quick(t-);
mul(c,c,a);
for i:= to len do
if ed[i].po=e then ans:=(ans+c[,i]) mod mo;
writeln(ans mod mo);
end.