There's a colored ring on the table. The ring has \textbf{k} sectors, and \textbf{i}-th sector has color \textbf{i} (all \textbf{k} colors are pairwise distinct). Sectors are numbered consecutively in clockwise direction. Kanga allowed Baby Roo to write \textbf{n} different integers from \textbf{1} to \textbf{n} on the ring. Number \textbf{i} should be written either on sector with color \textbf{x_i}, said Kanga, or on any other that is at most \textbf{a_i} sectors counterclockwise far from \textbf{x_i} or at most \textbf{b_i} sectors clockwise far. Kanga said that the numbers are written correctly if the above restrictions are met, each sector has at most one number written on it and the numbers \textbf{1}, \textbf{2}, ..., \textbf{n} are ordered in clockwise direction: if we start from the sector where we wrote \textbf{1} and go clockwise, we meet the other numbers in order \textbf{2}, \textbf{3}, ..., \textbf{n} and then \textbf{1} again. Now Baby Roo wants to know how many different ways are there to spoil the colored ring by writing the numbers correctly. Please note that it doesn't matter what number you write on the sector to get it spoiled. \InputFile First line contains two integers \textbf{n} and \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{15}, \textbf{1} ≤ \textbf{k} ≤ \textbf{60}, \textbf{n} ≤ \textbf{k}). Each of the next \textbf{n} lines contains three integers \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}). The numbers \textbf{x_i} are sorted in strictly increasing order. \OutputFile Output the number of different ways to spoil the ring.