34940번 - 구간 합

문제

$N$개의 구간 $[s_i, e_i]$과 값 $v_i$가 존재한다. 이 때, $f(l, r, n)$을 $l \le s_i \le e_i \le r$인 모든 $i$에 대한 $n^{v_i}$의 곱이라 하자.

1ドル \le l \le r \le M$인 모든 가능한 $[l, r]$ 구간에 대해, $f(l, r, r-l+1)$의 곱을 10ドル^9+7$로 나눈 나머지를 구하여라.

입력

첫 번째 줄에 $N$과 $M$이 차례대로 주어진다. (1ドル \le N, M \le 10^6$)

두 번째 줄부터 $N$개의 줄에 걸쳐, 각 줄에 $s_i,ドル $e_i,ドル $v_i$가 차례대로 주어진다. (1ドル \le s_i \le e_i \le M,ドル 1ドル \le v_i \le 10^6$)

입력으로 주어지는 수는 모두 정수이다.

출력

첫 번째 줄에 답을 출력한다.

제한

노트