← 返回题目列表

Codeforces · 1396/D

D. 彩虹矩形

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

Shrimpy Duc 是一个又胖又贪吃的男孩,总是很饿。经过一段时间的寻找食物来满足他永无休止的饥饿之后,Shrimpy Duc 发现 M&M 糖果无人看管地躺在 $$$L \times L$$$ 网格上。网格上有 $$$n$$$ M&M 糖果,第 $$$i$$$ 个 M&M 当前位于 $$$(x_i + 0.5, y_i + 0.5),$$$,并且颜色为 $$$c_i$$$,共有 $$$k$$$ 种颜色(M&M 的大小无关紧要)。

Shrimpy Duc 想要窃取一个矩形的 M&Ms,具体来说,他想要选择网格内具有整数坐标的矩形并窃取该矩形内的所有糖果。虾德克不需要偷走每一颗糖果,但是,他想每种颜色至少偷走一颗糖果。

也就是说,他要选择一个边与坐标轴平行的矩形,其左下顶点$$$(X_1, Y_1)$$$和右上顶点$$$(X_2, Y_2)$$$为整数坐标满足$$$0 \le X_1 < X_2 \le L$$$和$$$0 \le Y_1 < Y_2 \le的点L$$$,因此对于每种颜色 $$$1 \le c \le k$$$,至少有一个颜色为 $$$c$$$ 的 M&M 位于该矩形内。

这样的矩形有多少个?这个数字可能很大,因此您只需对 $$$10^9 + 7$$$ 求模即可。

输入

第一行包含三个正整数 $$$n, k, L$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^3, 1 \leq L \leq 10^9 )$$$ — 分别是 M&M 的数量、颜色的数量和网格的长度。

以下 $$$n$$$ 点描述了 M&M 巧克力豆。每行包含三个整数 $$$x_i, y_i, c_i$$$ $$$(0 \leq x_i, y_i < L, 1 \le c_i \le k)$$$ — 分别是第 $$$i$$$ 个 M&M 的坐标和颜色。

不同的 M&M 具有不同的坐标(对于每个 $$$i \ne j$$$,$$$x_i \ne x_j$$$ 或 $$$y_i \ne y_j$$$),并且对于每个 $$$1 \le c \le k$$$,至少有一个颜色为 $$$c$$$ 的 M&M。

输出

输出一个整数 — 满足 Shrimpy Duc 条件的矩形数量,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

4 2 4
3 2 2
3 1 1
1 1 1
1 2 1

输出 #1

20

输入 #2

5 3 10
6 5 3
5 3 1
7 9 1
2 3 2
5 0 2

输出 #2

300

输入 #3

10 4 10
5 4 4
0 0 3
6 0 1
3 9 2
8 7 1
8 1 3
2 1 3
6 3 2
3 5 3
4 3 4

输出 #3

226

注意

第一个样本的网格: