配点 : 300 点
問題文
托尔是一个喜欢数字序列的男孩。
当Toru像往常一样在客厅里欣赏数字序列时,他听到电视上出现了“多样性”这个词。
听到这个消息,Toru 想要为他拥有的数字序列添加多样性,因此他决定创建一个满足以下所有条件的序列。 N 整数元素序列 我决定制作 a_1, ..., a_N 。 在
- a_{l_i}, a_{l_i + 1}, ..., a_{r_i} 中 至少有一个值不同于 b_i 。 (1 \leq i \leq M)
- 所有元素的值为 1 以上 S 下面。
托尔很好奇有多少个数字序列满足这些条件,但他意识到自己很难数出。
让我们找出 Thor 可能的数字序列的数量。答案可能非常大,所以 请打印除以10^9 + 7 后的余数。
制約
- 所有输入均以整数形式给出。 所有
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq S \leq 10^5
- 1 \leq l_i \leq r_i \leq N
- 1 \leq b_i \leq S
- (l_i, r_i, b_i) 对都不同。
入力
输入是按以下格式从标准输入给出的。
N M S l_1 r_1 b_1 l_2 r_2 b_2 : l_M r_M b_M
出力
可能的序列总数 打印除以 10^9+7 后的余数。
入力例1
3 2 2 1 2 1 2 3 2
出力例1
4
必须满足以下条件: 3 一。 至少
- a_1, a_2 至少 1 津叶 它是除 1 之外的整数。
- a_2, a_3 至少 1 津叶 它是除 2 之外的整数。
- 序列元素的所有值都是 1 以上 2 下面。
满足这个的序列是(1, 2, 1), (2, 1, 1), (2, 1, 2), (2, 2, 1) 的 4 有两个。 有一个正方形
入力例2
8 3 4 1 5 1 2 6 1 4 8 1
出力例2
65364
入力例3
7 6 4 1 5 1 3 6 3 2 2 4 5 7 4 4 7 2 2 2 3
出力例3
7984
入力例4
5 3 52657 1 2 1 4 5 1 1 5 1
出力例4
145394311
入力例5
8 10 3 1 5 1 6 8 2 2 6 2 3 7 1 8 8 3 1 3 3 4 8 1 5 6 3 3 7 2 1 8 2
出力例5
3439