Russian Lotto
To play "Russian Lotto," cards are used that adhere to the following rules:
Each card has 3 rows and N columns.
Each row contains K cells filled with integers, while the remaining cells are left empty.
In the i-th column, numbers can only be selected from the range a_i to b_i.
No number can appear more than once on the same card.
Here is an example of such a card:
Your task is to determine the number of different possible cards.
Input
The first line contains two integers, N and K (3 ≤ K ≤ 9, 1 < K < N). Each of the next N lines contains two non-negative integers, a_i and b_i, each not exceeding 1000. It is guaranteed that a_i < b_i, b_i < a_{i+1}, and b_i - a_i < 20.
Output
The program should output a single integer, representing the total number of different cards possible.