Кольцо
На столе лежит разноцветное кольцо. Оно имеет 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 (1 ≤ n ≤ 15, 1 ≤ k ≤ 60, n ≤ k). Каждая из следующих n строк содержит три целых числа x_i, a_i, b_i (1 ≤ x_i ≤ k; 0 ≤ a_i, b_i; a_i + b_i < k). Числа x_i отсортированы в строго возрастающем порядке.
Выходные данные
Вывести количество способов, которыми можно испортить кольцо.