Гірські стежки#1773
Турист планує тренувальні маршрути в горах. Для тренування є спеціальний майданчик з контрольними точками, пронумерованими від до , і стежками. Кожна стежка може бути пройдена лише в одному напрямку (вгору або вниз). Кожна стежка має рейтинг складності. Між двома точками може бути кілька стежок, а також може бути кільцева стежка (початок і кінець збігаються).
Маршрут — це непорожня послідовність стежок, така, що кожна наступна (крім першої) починається там, де закінчилася попередня. Корисний тренувальний маршрут — це такий, в якому складність кожної стежки (крім першої) строго більша за складність попередньої.
Турист повинен обрати маршрут, який починається і закінчується в базовому таборі (точка ). Він може розглядати лише корисні тренувальні маршрути.
Потрібно порахувати, скільки різних корисних тренувальних маршрутів доступно туристу. Оскільки їх може бути дуже багато, виведіть залишок від ділення їх кількості на .
У першому рядку містяться цілі числа і . Кожен з наступних рядків містить числа A_i, B_i, C_i — початок і кінець -ї стежки та її складність.
1 \leq N \leq 50000, 1 \leq M \leq 100000, 1 \leq C_i \leq 30000.
Виведіть одне ціле число — кількість корисних тренувальних маршрутів за модулем .
Приклад 1