宝宝容斥。

记 $\text{Ans}_{s,t,k}$ 表示从 $s$ 走到 $t$ 中途不经过 $s,t$ 且恰好走 $k$ 步的答案。发现直接处理只能限定 $s,t$ 中一端不经过，故我们需要容斥。我们钦定路径 $s$ 一端始终没有重复经过，容斥去 $t$ 的重复经过。此时总方案数为从 $s$ 走 $k$ 步到 $t$ 但中途不重复经过 $s$ 的方案数，记之为 $f_{s,t,k}$。对于重复经过 $t$ 但不重复经过 $s$ 的非法路径，划分其为两阶段，枚举第一次经过 $t$ 走了 $d$ 步，首先从 $s$ 走 $d$ 步到 $t$ 且都不经过 $s,t$，再从 $t$ 走 $k-d$ 步回到 $t$，但是不经过 $s$，其中 $1\le d<k$。发现一阶段的方案数就是 $\text{Ans}_{s,t,d}$，记 $g_{s,t,k}$ 表示从 $s$ 走 $k$ 步回到 $s$ 但不经过 $t$ 的方案数，那么二阶段方案数为 $g_{t,s,k-d}$。于是我们有：

$$\text{Ans}_{s,t,k}=f_{s,t,k}-\sum_{d=1}^{k-1}\text{Ans}_{s,t,d}\times g_{t,s,k-d}.$$

$f$ 是好处理的，枚举起点 $s$，初始 $f_{s,s,0}=1$，枚举步数 $d$，转移 trivial：$f_{s,u,d} \to f_{s,v,d+1}$，要求存在边 $(u,v)$ 且 $v \ne s$。

考虑如何处理 $g$。再次容斥。用 $t$ 走 $k$ 步回到 $t$ 的总方案数减去其中经过了 $s$ 的非法方案数。记 $h_{s,t,k}$ 表示 $s$ 走 $k$ 步到 $t$ 无任何限制的方案数，总方案数即 $h_{s,s,k}$。对于非法路径，我们类似地划分其为两阶段，枚举最后一次经过 $t$ 走了 $d$ 步，首先从 $s$ 走 $d$ 步到 $t$ 无其他限制，再从 $t$ 走 $k-d$ 步回到 $s$ 但中途不重复回到 $t$。前者即 $h_{s,t,d}$，后者即 $f_{t,s,k-d}$。于是我们有：

$$g_{s,t,k}=h_{s,s,k}-\sum_{d=1}^{k-1} h_{s,t,d}\times f_{t,s,k-d}.$$

$h$ 类似 $f$，处理 naive。初始 $h_{s,s,0}=1$，枚举步数 $d$，转移 $h_{s,u,d}\to h_{s,v,d}$，只要求 $(u,v)$ 有边。

得到 $g$ 后处理 $\text{Ans}$。最后 $O(1)$ 输出答案。处理 $f,h$ 复杂度 $O(n^3d)$，处理 $g,\text{Ans}$ 复杂度 $O(n^2d^2)$。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 110;
const int M = 55;
int n, Q, m; ull P; bool e[N][N];
ull F[M][N][N], H[M][N][N], Ans[M][N][N], G[M][N][N];
int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> m >> P;
	for (int i = 1, u, v; i <= m; i ++)
		cin >> u >> v, e[u][v] = 1;
	for (int s = 1; s <= n; s ++) {
		F[0][s][s] = H[0][s][s] = 1;
		for (int k = 1; k <= 50; k ++) for (int t = 1; t <= n; t ++) for (int v = 1; v <= n; v ++)
			if (e[t][v]) (H[k][s][v] += H[k - 1][s][t]) %= P;
		for (int k = 1; k <= 50; k ++) for (int t = 1; t <= n; t ++) for (int v = 1; v <= n; v ++)
			if (e[t][v] && v != s) (F[k][s][v] += F[k - 1][s][t]) %= P;
	}
	for (int s = 1; s <= n; s ++) for (int t = 1; t <= n; t ++) if (s != t) {
		for (int k = 1; k <= 50; k ++) {
			for (int d = 1; d < k; d ++) 
				G[k][s][t] = (G[k][s][t] + H[d][s][t] * F[k - d][t][s] % P) % P;
			G[k][s][t] = (H[k][s][s] + P - G[k][s][t]) % P;
		}
	}
	for (int s = 1; s <= n; s ++) for (int t = 1; t <= n; t ++) if (s != t) {
		for (int k = 1; k <= 50; k ++) {
			for (int d = 1; d < k; d ++)
				Ans[k][s][t] = (Ans[k][s][t] + Ans[d][s][t] * G[k - d][t][s] % P) % P;
			Ans[k][s][t] = (F[k][s][t] + P - Ans[k][s][t]) % P;
		}
	}
	cin >> Q; int x, y, k;
	while (Q --) {
		cin >> x >> y >> k; cout << Ans[k][x][y] << "\n";
	}
	return 0;
}