For a permutation of $1, 2, \ldots, n$, let $s_i$ be the length of the shortest contiguous subarray containing all values $1, 2, \ldots, i$.

Let $\operatorname{pos}_p(x)$ be the position of $x$ in the permutation; we have

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

For each $i$, an interval constraint $[l_i, r_i]$ is given.

Please count the permutations satisfying $l_i \le s_i \le r_i$ for every $i$. Print the answer modulo $998244353$.

Input

The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

Output

Print the number of valid permutations modulo $998244353$.

Please note that a valid permutation may not exist.

Examples

Input 1

3
1 1
2 2
3 3

Output 1

4

Note

The valid permutations in the example are $(1, 2, 3)$, $(2, 1, 3)$, $(3, 1, 2)$, and $(3, 2, 1)$.