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

문제

Глубоко под землей, в злодейской лаборатории Грю, обитает несметное количество миньонов. Чтобы как-то разнообразить жизнь желтых существ, Грю решил каждый месяц проводить лотерею. Лотерея проходит следующим образом: каждому миньону дается массив длины n, в котором все элементы — целые положительные числа, не превосходящие k.

Затем Грю оглашает список из m троек чисел l_i, r_i, x_i. В лотерее выигрывают те миньоны, массив которых обладает свойством: если для каждого i рассмотреть элементы массива с номерами от l_i до r_i, то максимальным среди этих элементов в массиве миньона будет число x_i.

Грю стало интересно, сколько миньонов придут к нему за призами. Помогите ему!

Считается, что каждый возможный массив достался ровно одному миньону. Поскольку ответ может быть довольно большим, выведите остаток деления искомого числа победителей на 10⁹ + 7.

입력

В первой строке находятся три целых числа n, m, k (1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ k ≤ 10⁹) — размер массивов, число запросов и максимальное число, которое может встретиться в массиве. В следующих m строках дано по три числа l_i, r_i, x_i (1 ≤ l ≤ r ≤ n, 0 ≤ x_i ≤ k) — список троек Грю.

출력

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

제한

힌트