3946. 信使

【题目描述】

小 C 最近刚刚应聘成为了 B 国的皇家信使。他的第一份任务是要将一封信从城镇 $u$ 送到城镇 $v$。小 C 并不打算沿最短路送信，他想顺便去一些其他城镇旅游。

B 国的道路都是单行路，每条路从一个城镇连向另一个城镇。由于想尽可能充分利用任务要求的时间，小 C 想从城镇 $u$ 出发，在走过 $d$ 段路后恰好到达城镇 $v$。为了避免引起发信或收信的城镇的官员的怀疑，小 C 只会经过城镇 $u$ 和城镇 $v$ 各一次（即起点和终点那一次），但是他可以经过其他城镇任意多次，也可以经过任意一条路任意多次。

现在小 C 想知道满足上述条件的路径数量。由于答案可能很大，只需输出答案对一个正整数 $z$ 取模的结果。

【输入格式】

输入第一行包含三个非负整数 $n, m, z$，分别表示 B 国的城镇数、道路数，以及模数。

接下来 $m$ 行，每行两个正整数 $a, b$，表示有一条从城镇 $a$ 到城镇$b$ 的单向道路。

接下来一行一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行三个正整数 $u, v, d$，表示一次询问。

【输出格式】

输出 $q$ 行，每行一个非负整数，表示一次询问的答案对 $z$ 取模的结果。

【输入样例】

5 7 10
1 2
2 3
3 4
4 5
5 1
2 4
4 1
2
2 1 3
5 3 6

【输出格式】

2
1

【样例说明】

对于第一次询问，可能的路径有 $2\rightarrow 3\rightarrow 4\rightarrow 1$ 和 $2\rightarrow 4\rightarrow 5\rightarrow 1$。

对于第二次询问，可能的路径只有 $5\rightarrow 1\rightarrow 2\rightarrow 4\rightarrow 1\rightarrow 2\rightarrow 3$。

【数据规模和约定】

对于前 $10\%$的数据，$d \leq 5$；

对于前 $30\%$的数据，$n \leq 5，q \leq 100$；

对于前 $60\%$的数据，$n \leq 30，q \leq 100$；

对于$100\%$的数据，$2 \leq n \leq 100，0 \leq m \leq n * (n – 1)，2 \leq z \leq 10^9，1 \leq q \leq 500000，1 \leq d \leq 50$，$1 \leq a, b, u, v \leq n，a ≠ b，u ≠ v$，题目保证没有重边。