29180번 - Лотерея 다국어

Глубоко под землей, в злодейской лаборатории Грю, обитает несметное количество миньонов. Чтобы как-то разнообразить жизнь желтых существ, Грю решил каждый месяц проводить лотерею. Лотерея проходит следующим образом: каждому миньону дается массив положительных чисел размером $n$, в котором каждый элемент не превосходит $k$. Затем Грю оглашает список из $m$ троек числел $l_i$, $r_i$, $x_i$. В лотерее выигрывают те миньоны, массив которых обладает свойством: если для каждого $i$ из оглашенного списка рассмотреть числа $l_i$ и $r_i$ как границы запроса <<максимум на отрезке>>, то ответом на этот запрос в массиве миньона будет число $x_i$. Грю стало интересно, сколько миньонов придут к нему за призами, помогите ему! Считается, что миньонов так много, что каждый описанный выше массив достался ровно одному миньону. Поскольку число может быть слишком большим, выведите остаток от него при делении на $10^9 + 7$.

В первой строке входного файла даны три числа $n, m, k$ ($1 \le n \le 100\,000$, $1 \le m \le 100\,000$, $1 \le k \le 1000\,000\,000$) --- размер массивов, число запросов и максимальное число, которое может встретиться в массиве. В следующих $m$ строках дано по три числа $l_i$, $r_i$, $x_i$ ($1 \le l \le r \le n$, $1 \le x_i \le k$) --- описание $i$-го запроса.

В единственной строке выходного файла выведите отстаток от деления числа выйгравших миньонов на $10^9 + 7$.