32140번 - 낭만고양이

문제

나는 낭만고양이 ~♪

슬픈 도시를 비춰 춤추는 작은 별빛 ☆

피돌이가 바라보는 밤하늘에는 $N$개의 별들이 놓여있으며 각각의 별은 $M$가지 색상 중 하나의 색으로 빛나고 있다.

도시를 비추는 별빛이 얼마나 되는지 궁금했던 피돌이는 다음과 같은 사실을 알아냈다.

임의의 서로 다른 4ドル$개의 별들을 선택하였을 때 선택한 별들을 꼭짓점으로 가지는 사각형이 $x, y$ 축과 변이 평행한 정사각형이며 정사각형의 꼭짓점과 테두리 위에 있는 모든 별의 색깔이 같다면 정사각형 넓이만큼의 별빛을 도시에 비추고 있다.

낭만에 젖어 있는 피돌이를 대신해 도시를 비추는 모든 별빛의 합을 구해보자.

입력

첫째 줄에 $N$과 $M$이 공백을 두고 주어진다. $(1 \leq M \leq N \leq 300,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 별들의 정보인 $x_i, y_i, z_i$ 가 공백을 사이에 두고 주어진다. 이는 별이 $(x_{i}, y_{i})$에 위치하며 색깔이 $z_{i}$라는 의미이다. $(0 \leq x_i, ,円 y_i \leq 10^9 ; 1 \leq z_i \leq M)$

모든 별의 위치는 다르다.

출력

첫째 줄에 도시를 비추는 모든 별빛의 합을 출력한다. 단, 수가 매우 커질 수 있으므로 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

힌트