Кільце
На столі лежить різнокольорове кільцо. Воно має 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 відсортовано у строго зростаючому порядку.
Вихідні дані
Вивести кількість способів, якими можна пошкодити кільце.