На столі лежить різнокольорове кільцо. Воно має \textbf{k} секторів, \textbf{i}-ий сектор має колір \textbf{i} (усі \textbf{k} кольорів попарно різні). Сектори послідовно пронумеровані за годинниковою стрілкою. Канга пропонує Малюку Ру написати на кільці \textbf{n} різних цілих чисел від \textbf{1} до \textbf{n}. Число \textbf{i} слід написати або на секторі кольору \textbf{x_i}, або на довільному іншому, який знаходиться не далі \textbf{a_i} секторів від \textbf{x_i} проти годинникової стрілки, або не далі ніж \textbf{b_i} секторів за годинниковою стрілкою. Канга повідомив, що усі числа записані коректно з врахуванням вище наведених умов, у кожному секторі записано як мінімум одне число, а числа \textbf{1}, \textbf{2}, ..., \textbf{n} розміщені за годинниковою стрілкою: якщо почати рух від сектора, на якому записана \textbf{1} за годинниковою стрілкою, то порядок чисел буде \textbf{2}, \textbf{3}, ..., \textbf{n} і знову \textbf{1}. Малюк Ру хоче знати кількість способів, якими він може пошкодити різнокольорове кільце записавши на ньому числа у правильному порядку. Щоб пошкодити кільце - не важливо які числа Ви на ньому пишете. \InputFile Перший рядок містить два цілих числа \textbf{n} та \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{15}, \textbf{1} ≤ \textbf{k} ≤ \textbf{60}, \textbf{n} ≤ \textbf{k}). Кожен з наступних \textbf{n} рядків містить три цілих числа \textbf{x_i}, \textbf{a_i}, \textbf{b_i} (\textbf{1} ≤ \textbf{x_i} ≤ \textbf{k}; \textbf{0} ≤ \textbf{a_i}, \textbf{b_i}; \textbf{a_i + b_i} < \textbf{k}). Числа \textbf{x_i} відсортовано у строго зростаючому порядку. \OutputFile Вивести кількість способів, якими можна пошкодити кільце.