想到了Floyd，但不会求路径数

题目：

回家

1000ms/256mb

题目描述

给一张 $n$ 个点，$m$ 条边没有边权的有向图，问从一个点 $s$ 到另一个点 $t$ 经过边数最少的路径有多少条。

H 城的交通路线可以看做为一个 $n$ 个点，$m$ 条边的有向图，边权均为 1，小 Z 打算从学校( $S$ 点) 回到家中 ($T$ 点)。

小 Z 比较懒，总是会⾛从 $S$ 到 $T$ 经过边的数量最少的那些路径，⽽小 Z 又不想⾛重复的路径。

所以小 Z 想让你算算，在这个图中，从 S 走到 T 的不同的经过边数最少的路径有多少条？

由于答案可能很大，所以只需要输出答案除以 $p$ 的余数。如果 $S$ 无法走到 $T$，那么请输出 0。 　

数据输入

第一行三个整数 $n,m,p,s,t$。

接下来 $m$ 行，每行两个整数 $x,y$，表示 $x$ 到 $y$ 有一条边。

数据输出

⼀⾏⼀个整数，答案除以 $p$ 的余数。

样例输入 #1

4 5 1000 1 4
1 2
1 3
2 4
3 4
2 3

样例输出 #1

2

数据规模

对于 $30\%$ 的数据，$n,m \le 20$。

对于 $60\%$ 的数据，$n,m \le 1000$。

对于 $100\%$ 的数据，$n,m \le 10^6,1 \le s, t, x, y \le n, 2 \le p \le 10^8$。