在 Byteotia 王国长期统治后，Byteasar 退位了，他太累了，无法继续治理国家。很快他意识到，他怀念了解宫廷新闻、政策和阴谋的日子。因此，为了保持联系，他决定成为一名皇家信使。

在他新工作的第一天，他受命将一封紧急信件从一个城镇送到另一个城镇。Byteasar 并没有让他的第一次旅行尽可能及时，而是决定将其变成一次全国巡游，以便在担任国王多年后恢复体力。当然，他会采取一些预防措施，以免新国王发现信使行程的真实性质。

Byteotia 的所有道路都是单向的，直接从一个城镇通往另一个城镇。Byteasar 已经宣布了他想要在旅途中经过的道路段的确切数量，而不管实际需要多少段。为了不引起皇家官员的怀疑，他坚持只访问起点城镇和终点城镇各一次，但他愿意多次访问任何其他城镇，也可以多次经过同一条道路段。

请编写一个程序，帮助我们的英雄确定满足他要求的路线数量。换句话说，程序需要确定在给定的一对城镇之间，访问起点和终点各一次且长度为给定值的不同路线数量。由于这个数字可能非常大，返回它除以 Byteasar 选择的某个数的余数即可。

输入格式

标准输入的第一行包含三个整数 $n, m$ 和 $z$ ($n \ge 2, 0 \le m \le n(n - 1), 2 \le z \le 1\,000\,000\,000$)，分别表示 Byteotia 的城镇数量、城镇之间的单向道路数量以及 Byteasar 选择的除数。城镇编号从 $1$ 到 $n$。

接下来 $m$ 行，每行包含一对整数 $a, b$ ($1 \le a, b \le n, a \neq b$)，由空格分隔，表示存在一条从城镇 $a$ 到城镇 $b$ 的直接单向道路。输入中不会重复出现同一条道路段。

下一行包含一个正整数 $q$，表示 Byteasar 的查询次数。接下来的 $q$ 行，每行包含一个查询。查询由三个整数 $u_i, v_i$ 和 $d_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le d_i \le 50$) 组成，由空格分隔，表示 Byteasar 想要通过恰好 $d_i$ 条道路段从城镇 $u_i$ 前往城镇 $v_i$。

输出格式

输出应包含恰好 $q$ 行。第 $i$ 行应包含第 $i$ 个查询所要求的路线数量除以 $z$ 的余数。

样例

输入格式 1

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

输出格式 1

2
1

说明

样例说明：有两个路线满足第一个查询：$2 \to 3 \to 4 \to 1$ 以及 $2 \to 4 \to 5 \to 1$；只有一个路线满足第二个查询：$5 \to 1 \to 2 \to 4 \to 1 \to 2 \to 3$。

子任务

测试集由以下子任务组成。在每个子任务中，可能包含多个测试组。