Російське лото

Для гри в "російське лото" використовуються картки, які відповідають наступним умовам:

• картка складається з 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.

Вихідні дані

Програма повинна вивести одне число - кількість можливих карток.

Приклади