問題文

岩井星人さんの某名言、一般化しようと思いませんか？

kazuppa君は競技プログラミングのコンテストを開催することになりました。kazuppa君は $N$ 問の原案を持っており、 $i$ 番目の原案の難易度は $L_i$ 以上 $R_i$ 以下になることがわかっていますが、具体的にいくつになるかはコンテスト終了後までわかりません。

コンテストでは原案を並べ替えて出題します。具体的には、$(1,2,...,N)$ の順列 $p=(p_1,p_2,...,p_N)$ を決めて $i$ 番目の原案をコンテストの $p_i$ 番目の問題として出題することにします。

ここで、とある競技プログラミングのコンテストにおいて、$4$ 番目の問題が $5$ 番目の問題よりも難しかったせいで、SNS で煽り画像が拡散されてしまいました。
この世界には、全ての $1 ≤ d ≤ N$ について、 $d$ 番目の問題が解けなかったことを嘲笑する煽り画像が存在するので、煽り画像の拡散を防ぎたいkazuppa君は、次が成り立つ可能性が残るように原案を並べ替える必要があります。

• 全ての $1 \leq d \lt N$ について、$d$ 番目の問題の難易度が $d + 1$ 番目の問題の難易度以下である。

煽り画像（折りたたみ）

このとき、条件を満たす原案の並べ替え方 $p$ は全部で何通りありますか？

より厳密には、以下の条件を満たす $(1,2,...,N)$ の順列 $p = (p_1,p_2,...,p_N)$ の個数を数えてください。

• ある整数列 $(x_1,x_2,...,x_N)$ が存在し、次の二つの条件を共に満たす。
• 全ての $1\leq i\leq N$ について $L_{p_i}\leq x_i\leq R_{p_i}$
• 全ての $1\leq i< N$ について $x_i\leq x_{i+1}$

制約

• $N\in \{7,8\}$
• $1\leq L_i\leq R_i\leq 3854$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

条件を満たす $p$ の個数を出力せよ。

サンプル

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