$1, 2, \ldots, n$ の順列について、$s_i$ を、値 $1, 2, \ldots, i$ をすべて含む最短の連続部分配列の長さとします。

$\operatorname{pos}_p(x)$ を順列内での $x$ の位置とすると、次の式が成り立ちます。

$$ s_i = \max_{1 \le x \le i} \operatorname{pos}_p(x) - \min_{1 \le x \le i} \operatorname{pos}_p(x) + 1. $$

各 $i$ について、区間制約 $[l_i, r_i]$ が与えられます。

すべての $i$ について $l_i \le s_i \le r_i$ を満たす順列の個数を数えてください。答えを $998244353$ で割った余りを出力してください。

入力

最初の行には整数 $n$ ($1 \le n \le 2 \cdot 10^5$) が含まれます。

続く $n$ 行には、それぞれ 2 つの整数 $l_i$ と $r_i$ ($1 \le l_i \le r_i \le n$) が含まれます。

出力

条件を満たす順列の個数を $998244353$ で割った余りを出力してください。

条件を満たす順列が存在しない場合もあることに注意してください。

入出力例

入力 1

3
1 1
2 2
3 3

出力 1

4

注記

この例で条件を満たす順列は、$(1, 2, 3)$、$(2, 1, 3)$、$(3, 1, 2)$、$(3, 2, 1)$ です。