로또
시간 제한2초메모리 제한256 MB
길이 n이고 각 원소가 1부터 k까지인 배열 중, 주어진 m개 구간 [l,r]의 최댓값이 각각 지정된 x와 같은 배열의 개수를 구한다.
문제
지하 깊은 곳, 그루의 악당 실험실에는 수많은 미니언이 살고 있다. 노란 생물들의 삶에 활기를 불어넣기 위해 그루는 매달 로또를 열기로 했다. 로또는 다음과 같이 진행된다. 각 미니언에게는 길이 n인 배열이 주어지는데, 모든 원소는 k를 넘지 않는 양의 정수다.
그다음 그루는 m개의 삼중항 lᵢ, rᵢ, xᵢ 목록을 발표한다. 다음 성질을 만족하는 배열을 가진 미니언이 로또에서 당첨된다. 각 i에 대해 배열의 lᵢ번째부터 rᵢ번째까지의 원소를 볼 때, 그중 최댓값이 미니언의 배열에서 xᵢ이다.
그루는 상을 받으러 몇 명의 미니언이 올지 궁금해졌다. 그를 도와주자!
가능한 모든 배열은 정확히 한 미니언에게 주어진 것으로 본다. 답이 클 수 있으므로 당첨자 수를 109 + 7로 나눈 나머지를 출력한다.
입력
첫째 줄에 세 정수 n, m, k (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 1 ≤ k ≤ 109)가 주어진다. 이는 배열의 크기, 질의의 수, 배열에 나타날 수 있는 최댓값이다. 다음 m개 줄에 세 수 lᵢ, rᵢ, xᵢ (1 ≤ l ≤ r ≤ n, 0 ≤ xᵢ ≤ k)가 주어진다. 이는 그루의 삼중항 목록이다.
출력
출력 파일의 유일한 줄에 당첨된 미니언 수를 109 + 7로 나눈 나머지를 출력한다.