P12742 [POI 2016 R3] 信使 Messenger

翻译来自于 [LibreOJ](https://loj.ac/p/5038)。

**题目译自 [XXIII Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi23-3/dashboard/) [Posłaniec](https://szkopul.edu.pl/problemset/problem/Mk-9GNDtSal6h_8T4n9Ezq9M/statement/)** 在统治拜托尼亚王国多年后，Byteasar 因疲惫不堪选择了退位。然而，很快他便怀念起宫廷的新闻、政策和阴谋。为了保持与王国的联系，他决定成为一名王室信使。 上任第一天，Byteasar 便受命将一封紧急信件从一座城镇送往另一座。但他并未选择最快送达，而是决定借此机会游历全国，放松自己多年执政的疲惫。当然，他会小心行事，确保新国王不会察觉他行程的真正目的。 拜托尼亚的所有道路均为单向，从一座城镇直达另一座。Byteasar 指定了他希望旅途中经过的道路段数，无论实际需要多少。为了不引起王室官员的怀疑，他要求起点和终点城镇各访问一次，而其他城镇可多次访问，同一道路也可重复经过。 请帮助我们的英雄编写程序，计算满足他要求的路线数量，即从指定起点到终点、长度固定的不同路线数，其中起点和终点各访问一次。由于答案可能很大，只需返回其对 Byteasar 选择的除数取模的结果。

第一行包含三个整数 $n, m, z$ $(n \geq 2, 0 \leq m \leq n(n-1), 2 \leq z \leq 1000000000)$，分别表示拜托尼亚的城镇数量、单向道路数量和 Byteasar 选择的除数。城镇编号为 $1$ 至 $n$。 接下来的 $m$ 行，每行包含两个整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示存在一条从城镇 $a$ 到城镇 $b$ 的单向道路。每条道路在输入中至多出现一次。 下一行包含一个正整数 $q$，表示 Byteasar 的查询数量。 接下来的 $q$ 行，每行包含三个整数 $u_i, v_i, d_i$ $(1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq d_i \leq 50)$，表示 Byteasar 希望从城镇 $u_i$ 旅行到城镇 $v_i$，恰好经过 $d_i$ 条道路。

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个查询的路线数量对 $z$ 取模的结果。

**样例 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$。 **附加样例** 1. $n=6, q=10$，五个城镇两两之间均有双向道路，第六个城镇无任何道路连接。 2. $n=20, q=100$，城镇呈环形排列，环上相邻城镇间均有双向道路。 3. $n=100, q=500000$，拜托尼亚的地图呈三叉戟形状。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 20, q \leq 100$ | $12$ | | $2$ | $n \leq 100, m \leq 500, q \leq 100$ | $20$ | | $3$ | $n \leq 100, q \leq 10000$ | $38$ | | $4$ | $n \leq 100, q \leq 500000$ | $30$ |