낭만고양이

나는 낭만고양이 ~♪

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

피돌이가 바라보는 밤하늘에는 $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$로 나눈 나머지를 출력한다.