Русское лото

Для игры в "русское лото" используются карточки,удовлетворяющие условиям:

• карточка состоит из 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.

Выходные данные

Программа должна вывести одно число - искомое количество карточек.

Примеры