← 返回题目列表

AtCoder · kupc2018_h

H. 彩色数字序列

中文机器翻译题面 查看原题

配点 : 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