Для игры в "русское лото" используются карточки,удовлетворяющие условиям:
карточка состоит из 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.
Программа должна вывести одно число - искомое количество карточек.