Problem Statement

Don't you want to generalize a certain famous quote by Iwai Seijin?

Kazuppa is going to hold a competitive programming contest. He has $N$ draft problems. The difficulty of the $i$-th draft is known to be between $L_i$ and $R_i$, inclusive, but its exact value will not be known until after the contest ends.

In the contest, the drafts are rearranged before being presented. Specifically, he decides on a permutation $p=(p_1,p_2,...,p_N)$ of $(1,2,...,N)$ and presents the $i$-th draft as the $p_i$-th problem of the contest.

Now, in a certain competitive programming contest, because the $4$-th problem was harder than the $5$-th problem, a taunting image spread across social media.
In this world, for every $1 ≤ d ≤ N$, there exists a taunting image mocking those who could not solve the $d$-th problem. To prevent such images from spreading, Kazuppa must rearrange the drafts so that it remains possible that the following holds.

• For all $1 \leq d \lt N$, the difficulty of the $d$-th problem is at most the difficulty of the $d + 1$-th problem.

Taunting image (collapsed)

How many ways $p$ of rearranging the drafts satisfy the condition?

More precisely, count the number of permutations $p = (p_1,p_2,...,p_N)$ of $(1,2,...,N)$ satisfying the following condition.

• There exists an integer sequence $(x_1,x_2,...,x_N)$ satisfying both of the following two conditions.
• For all $1\leq i\leq N$, $L_{p_i}\leq x_i\leq R_{p_i}$
• For all $1\leq i< N$, $x_i\leq x_{i+1}$

Constraints

• $N\in \{7,8\}$
• $1\leq L_i\leq R_i\leq 3854$
• All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_N\ R_N$

Output

Print the number of permutations $p$ satisfying the condition.

Sample

8
5 15
40 110
700 1400
600 800
900 1500
1800 2300
2100 2500
2400 3000

9

7
12 12
54 54
128 128
1310 1310
1193 1193
1806 1806
2876 2876

1