낭만고양이

나는 낭만고양이 ~♪

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

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