eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кольцо

Кольцо

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

На столе лежит разноцветное кольцо. Оно имеет k секторов, i-ый сектор имеет цвет i (все k цветов попарно различны). Сектора последовательно пронумерованы по часовой стрелке. Канга предлагает Малышу Ру написать на кольце n различных целых чисел от 1 до n. Число i следует написать либо на секторе цвета x_i, либо на любом другом, находящемся не дальше a_i секторов от x_i против часовой стрелки, или не дальше чем b_i секторов по часовой стрелке.

Канга сообщил, что все числа записаны корректно с учетом выше приведенных условий, в каждом секторе записано как минимум одно число, а числа 1, 2, ..., n расположены по часовой стрелке: если начать движение от сектора, на котором записана 1 по часовой стрелке, то порядок чисел будет 2, 3, ..., n и снова 1.

Малыш Ру хочет знать количество способов, которыми он может испортить разноцветное кольцо записав на нем числа в правильном порядке. Чтобы испортить кольцо - не важно какие числа Вы на нем пишете.

Входные данные

Первая строка содержит два целых числа n и k (1n15, 1k60, nk). Каждая из следующих n строк содержит три целых числа x_i, a_i, b_i (1x_ik; 0a_i, b_i; a_i + b_i < k). Числа x_i отсортированы в строго возрастающем порядке.

Выходные данные

Вывести количество способов, которыми можно испортить кольцо.

Пример

Входные данные #1
1 5
1 2 1
Выходные данные #1
4