시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 0 | 0 | 0 | 0.000% |
Глубоко под землей, в злодейской лаборатории Грю, обитает несметное количество миньонов. Чтобы как-то разнообразить жизнь желтых существ, Грю решил каждый месяц проводить лотерею. Лотерея проходит следующим образом: каждому миньону дается массив длины n, в котором все элементы — целые положительные числа, не превосходящие k.
Затем Грю оглашает список из m троек чисел li, ri, xi. В лотерее выигрывают те миньоны, массив которых обладает свойством: если для каждого i рассмотреть элементы массива с номерами от li до ri, то максимальным среди этих элементов в массиве миньона будет число xi.
Грю стало интересно, сколько миньонов придут к нему за призами. Помогите ему!
Считается, что каждый возможный массив достался ровно одному миньону. Поскольку ответ может быть довольно большим, выведите остаток деления искомого числа победителей на 109 + 7.
В первой строке находятся три целых числа n, m, k (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 1 ≤ k ≤ 109) — размер массивов, число запросов и максимальное число, которое может встретиться в массиве. В следующих m строках дано по три числа li, ri, xi (1 ≤ l ≤ r ≤ n, 0 ≤ xi ≤ k) — список троек Грю.
В единственной строке выходного файла выведите остаток от деления числа выигравших миньонов на 109 + 7.
5 3 5 1 3 2 1 2 1 1 5 5
9
Contest > Russian Code Cup > 2015 > RCC 2015 Warm-up E번