복권

땅 속 깊은 곳, 그루의 악당 연구소에는 셀 수 없이 많은 미니언이 살고 있다. 노란 이 존재들의 생활에 변화를 주려고, 그루는 매달 복권을 열기로 했다. 복권은 다음과 같이 진행된다. 각 미니언에게는 크기가 $n$인 양의 정수 배열이 주어지며, 배열의 모든 원소는 $k$ 이하이다. 이후 그루는 $m$개의 세 쌍 $l_i$, $r_i$, $x_i$의 목록을 발표한다. 각 $i$에 대해 $l_i$와 $r_i$를 구간 최댓값 질의의 범위로 본다. 모든 $i$에 대해 그 질의의 답이 $x_i$인 배열을 가진 미니언이 당첨된다. 그루는 몇 명의 미니언이 상품을 받으러 올지 알고 싶어 한다. 미니언이 아주 많아서 위에서 설명한 배열 하나하나가 정확히 한 미니언에게 주어졌다고 가정한다. 수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 세 정수 $n$, $m$, $k$ ($1 \le n \le 100000$, $1 \le m \le 100000$, $1 \le k \le 1000000000$)가 주어진다. 각각 배열의 크기, 질의의 개수, 배열 원소의 최댓값이다. 이어지는 $m$개의 줄에는 각각 세 정수 $l_i$, $r_i$, $x_i$ ($1 \le l_i \le r_i \le n$, $1 \le x_i \le k$)가 주어지며, 이는 $i$번째 질의를 나타낸다.

당첨된 미니언의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.