P11288 [COTS 2017] 模板 Z1

译自 [Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2017/) 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\}$。 给定 $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)$ 取模后的结果。

#### 样例解释 样例 $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$。 | 子任务编号 | $n\le $ |得分 | | :--: | :--: | :--: | | $ 1 $ | $ 100 $ | $ 20 $ | | $ 2 $ | $ 10^3 $ | $ 30 $ | | $ 3 $ | $10^6$ | $ 50 $ |