Ivan 正在为学校信息学竞赛设计一道模板题。在这道题中，给定一个数列 $S = a_1, a_2, \dots, a_n$，其中 $0 \le a_j < H$，以及 $m$ 个形如 $x_j, y_j$ 的询问，满足 $1 \le x_j \le y_j \le n$。第 $j$ 个询问的答案是数列 $S$ 中在位置 $x_j$ 到 $y_j$（含两端）之间的最大值：$z_j = \max(a_{x_j}, a_{x_j+1}, \dots, a_{y_j})$。
Ivan 为这道题制作了一组极好的测试数据，但他丢失了原始数列 $S$。已知原始数列的长度 $n$、数列元素大小的限制 $H$，以及 $m$ 个询问 $x_j, y_j$ 及其对应的答案 $z_j$。
一个长度为 $n$ 的数列 $S$ 被称为“好的”，如果它由区间 $[0, H - 1]$ 内的整数组成，且对于每个询问 $x_j, y_j$，其对应的答案均为 $z_j$。
求好的数列 $S$ 的数量模 $10^9 + 7$ 的结果。
输入格式
第一行包含三个自然数 $n, m$ 和 $H$ —— 数列的长度、询问的数量以及数列元素大小的限制。
接下来的 $m$ 行中，第 $j$ 行包含三个整数 $x_j, y_j$ 和 $z_j$ ($1 \le x_j \le y_j \le n$, $0 \le z_j < H$) —— 表示第 $j$ 个询问及其对应的答案。
输出格式
输出一个整数 —— 好的数列的数量模 $10^9 + 7$ 的结果。
子任务
对于所有子任务，均满足 $1 \le m, H \le 10^6$。
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 20 | $n \le 100$ |
| 2 | 30 | $n \le 1\,000$ |
| 3 | 50 | $n \le 1\,000\,000$ |
样例
输入样例 1
3 2 3 1 2 1 2 2 0
输出样例 1
3
说明
由于第二个询问，元素 $a_2$ 必须为 $0$；因此，结合第一个询问，元素 $a_1$ 必须为 $1$。元素 $a_3$ 可以是任何小于 $H = 3$ 的非负整数。因此，所有好的数列 $S$ 分别为 $(1, 0, 0)$、$(1, 0, 1)$ 和 $(1, 0, 2)$。
输入样例 2
7 10 3 1 3 1 3 4 1 3 6 2 4 5 2 1 1 1 1 2 1 3 3 0 1 1 1 3 3 0 3 6 2
输出样例 2
18