Задачи
Русское лото
Русское лото
Для игры в "русское лото" используются карточки,удовлетворяющие условиям:
карточка состоит из 3-х строк и N столбиков;
K клеток в каждой строке заняты целыми числами (остальные свободны);
в i-м столбце могут находится только числа из диапазона a_i...b_i;
одно и то же число не может повторятся на одной и той же карточке.
Пример карточки:
Найти количество различных карточек.
Входные данные
Впервой строке записано два числа - N и K (3 ≤ K ≤ 9, 1 < K < N). В каждой их следующих N строк записано два неотрицательных числа a_i и b_i, непревышающие 1000. Гарантировано, что a_i < b_i, b_i < a_{i+1} и b_i-a_i < 20.
Выходные данные
Программа должна вывести одно число - искомое количество карточек.
Пример
Входные данные #1
9 5 1 9 10 19 20 29 30 39 40 49 50 59 60 69 70 79 80 90
Выходные данные #1
817687046204481600000