CF1396D.Rainbow Rectangles

Shrimpy Duc is a fat and greedy boy who is always hungry. After a while of searching for food to satisfy his never-ending hunger, Shrimpy Duc finds M&M candies lying unguarded on a $L \times L$ grid. There are $n$ M&M candies on the grid, the $i$-th M&M is currently located at $(x_i + 0.5, y_i + 0.5),$ and has color $c_i$ out of a total of $k$ colors (the size of M&Ms are insignificant).

Shrimpy Duc wants to steal a rectangle of M&Ms, specifically, he wants to select a rectangle with integer coordinates within the grid and steal all candies within the rectangle. Shrimpy Duc doesn't need to steal every single candy, however, he would like to steal at least one candy for each color.

In other words, he wants to select a rectangle whose sides are parallel to the coordinate axes and whose left-bottom vertex $(X_1, Y_1)$ and right-top vertex $(X_2, Y_2)$ are points with integer coordinates satisfying $0 \le X_1 \lt X_2 \le L$ and $0 \le Y_1 \lt Y_2 \le L$, so that for every color $1 \le c \le k$ there is at least one M&M with color $c$ that lies within that rectangle.

How many such rectangles are there? This number may be large, so you only need to find it modulo $10^9 + 7$.

虾米·杜克是一个又胖又贪吃的小男孩，总是饿着肚子。在四处寻找食物以满足他永无止境的饥饿感之后，虾米·杜克发现了一堆无人看管的M&M巧克力豆，它们散落在一个 $L \times L$ 的网格上。网格上共有 $n$ 颗M&M巧克力豆，其中第 $i$ 颗位于坐标 $(x_i + 0.5, y_i + 0.5)$ 处，颜色为 $c_i$（总共有 $k$ 种不同颜色；M&M豆的尺寸可忽略不计）。

虾米·杜克想偷走一个矩形区域内的所有M&M豆，具体而言，他希望选取一个顶点坐标均为整数的矩形（即该矩形完全位于网格内），并偷走该矩形内部的所有糖果。虾米·杜克并不需要偷走全部糖果，但他希望每种颜色至少偷到一颗。

换言之，他要选取一个边与坐标轴平行的矩形，其左下角顶点为 $(X_1, Y_1)$、右上角顶点为 $(X_2, Y_2)$，且 $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$ 取模的结果。

The first line contains three positive integers $n, k, L$ $(1 \leq k \leq n \leq 2 \cdot 10^3, 1 \leq L \leq 10^9 )$ — the number of M&Ms, the number of colors and the length of the grid respectively.

The following $n$ points describe the M&Ms. Each line contains three integers $x_i, y_i, c_i$ $(0 \leq x_i, y_i \lt L, 1 \le c_i \le k)$ — the coordinates and color of the $i$-th M&M respectively.

Different M&Ms have different coordinates ($x_i \ne x_j$ or $y_i \ne y_j$ for every $i \ne j$), and for every $1 \le c \le k$ there is at least one M&M with color $c$.

第一行包含三个正整数 $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 \lt 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 巧克力豆。

Output a single integer — the number of rectangles satisfying Shrimpy Duc's conditions, modulo $10^9 + 7$.

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

Grid for the first sample:

第一个样例的网格：