大禹治水

出题

上古时期洪水肆虐，大禹接受帝舜的任命前去治水。由于灾情紧急，所以大禹每天夜以继日地工作。期间他多次路过自己的家门口，却没有进去探望家人。最终，大禹花费十三年时间，耗尽心力，终于完成了治水大业。大禹也因此声名鹊起，得到了天下人的拥护和爱戴。

大禹在治水过程中经过 $n$ 个地点，从 $1$ 到 $n$ 对其进行编号，总共有 $m$ 条道路连接这些地方，大禹的家被编号为 $1$，与大禹的家仅相隔一条道路的地点都称为“家门口”，禹已经过这些地点无数次，他想知道，从家里出发，经过 $1$ 条道路、$2$ 条道路……$k$ 条道路之后，总共有多少种走法在不入家门的情况下能恰好到达家门口？由于走法可能非常多，需要将最终的走法对 $p$ 取余后输出。

“禹伤先人父鲧功之不成受诛，乃劳身焦思，居外十三年，过家门不敢入。”

——《史记 · 夏本纪》

输入

本题有多个测试点，每个测试点数据范围不同。

第一行为一个整数 $Case$，表示测试点编号；

第二行四个整数 $n,m,k,p$，分别表示地点数、道路数、最多可以经过的道路数与需要取余的模数；

接下去 $m$ 行，每行两个整数 $u,v$，表示在地点 $u$ 与 $v$ 之间有一条道路连接。

输出

对于每个测试点，输出方案数对 $p$ 取余后的结果。

样例输入

1
3 3 3 1000000007
1 2
2 3
3 1

样例输出

6

样例解释

大禹从家里 $1$ 出发，在 $3$ 条道路内行走而不入家门的所有走法有：

经过一条道路：

• 1 → 2
• 1 → 3

经过两条道路：

• 1 → 2 → 3
• 1 → 3 → 2

经过三条道路：

• 1 → 2 → 3 → 2
• 1 → 3 → 2 → 3

正好到达地点 $2$ 的有 $3$ 次，正好到达地点 $3$ 的也有 $3$ 次，而 $2$ 与 $3$ 都是“家门口”，因此在三条道路内恰好到达“家门口”的总走法有 $6$ 种。

数据范围

当 $Case\in[1,10]$ 时，$2\leq n,m,k\leq7,~p=10^9+7$；

当 $Case\in[11,30]$ 时，$2\leq n\leq50,~1\leq m\leq10^6,~1\leq k\leq10^6,~10^7\leq p\leq10^9$；

当 $Case\in[31,50]$ 时，$2\leq n\leq4,~1\leq m\leq10^6,~1\leq k\leq10^{100000},~1\leq p\leq3$；

对于所有 $Case$，$1\leq u,v\leq n$。

题解

左手边，再过两个胡同就到了。