#5038. 「POI2016 R3」信使 Messenger

题目译自 XXIII Olimpiada Informatyczna — III etap Posłaniec

题目描述

在统治拜托尼亚王国多年后，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$ 取模的结果。

样例

输入

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$。

附加样例

• $n=6$, $q=10$，五个城镇两两之间均有双向道路，第六个城镇无任何道路连接。
• $n=20$, $q=100$，城镇呈环形排列，环上相邻城镇间均有双向道路。
• $n=100$, $q=500000$，拜托尼亚的地图呈三叉戟形状。

数据范围与提示