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
注意
第一个样本的网格: