题目背景

译自 Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection) D2T2。$\texttt{4s,0.5G}$。

题目描述

题目（【模板】RMQ）。

给定整数序列 $a_1,a_2,\cdots,a_n$，值域为 $[0,h)$。

有 $m$ 次询问。第 $i$ 次询问给定 $l_i,r_i$，求出 $\displaystyle \max_{k\in [l_i,r_i]} \{a_k\}$。

在 Mitakihara Middle School 的校内 OJ 中，Madoka 精心造了这题的数据。然而粗心的 Homura 把这题的所有输入文件中的 $a$ 序列误删了。

现在她们拥有的信息只有 $n,m,h$，每个询问和对应的答案。她们很好奇一共有多少个可能的 $a$ 序列满足条件。请你帮忙求出答案对 $(10^9+7)$ 取模后的结果。

输入格式

第一行，三个正整数 $n,m,h$;

接下来 $m$ 行，每行三个整数 $l_i,r_i,x_i$，表示 $\displaystyle \max_{k\in [l_i,r_i]} \{a_k\}=x_i$。

输出格式

输出一行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

3 2 3
1 2 1
2 2 0

3

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

18

提示

样例解释

样例 $1$ 解释：只有 $[1,0,0]$，$[1,0,1]$，$[1,0,2]$ 满足条件。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n,m,h\le 10^6$；
• $1\le l_i\le r_i\le n$；
• $0\le x_i\lt h$。