Loto#812
To play "Loto," cards are used that satisfy the following conditions:
Each card consists of rows and columns.
In each row, exactly cells are filled with integers (the remaining cells are empty).
In the -th column, only numbers from the range a_i to b_i (inclusive) can be used.
The same number cannot appear more than once on the same card.
Example of a card:
Determine the number of different possible cards.
The first line contains two integers and (3 \le K \le 9, 1 < K < N). Each of the next lines contains two non-negative integers a_i and b_i (not exceeding ). It is guaranteed that a_i < b_i, b_i < a_{i+1}, and b_i - a_i < 20.
Output a single integer — the total number of different cards.
Example 1