Задачі
Русское лото
Русское лото
Для игры в "русское лото" используются карточки,удовлетворяющие условиям:
\begin{itemize}
\item карточка состоит из \textbf{3}-х строк и \textbf{N} столбиков;
\item \textbf{K} клеток в каждой строке заняты целыми числами (остальные свободны);
\item в \textbf{i}-м столбце могут находится только числа из диапазона \textbf{a_i...b_i};
\item одно и то же число не может повторятся на одной и той же карточке.
\end{itemize}
Пример карточки:
\includegraphics{https://static.e-olymp.com/content/9b/9b0d730d14d4f1f2cf2e58ca8d269a5fb6989d28.jpg}
Найти количество различных карточек.
\InputFile
Впервой строке записано два числа - \textbf{N} и \textbf{K} (\textbf{3} ≤ \textbf{K} ≤ \textbf{9}, \textbf{1} < \textbf{K} < \textbf{N}). В каждой их следующих \textbf{N} строк записано два неотрицательных числа \textbf{a_i} и \textbf{b_i}, непревышающие \textbf{1000}. Гарантировано, что \textbf{a_i} < \textbf{b_i}, \textbf{b_i} < \textbf{a_\{i+1\}} и \textbf{b_i}-\textbf{a_i} < \textbf{20}.
\OutputFile
Программа должна вывести одно число - искомое количество карточек.
Вхідні дані #1
9 5 1 9 10 19 20 29 30 39 40 49 50 59 60 69 70 79 80 90
Вихідні дані #1
817687046204481600000