G. Growing Prefix Span
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Example
Input
3
1 1
2 2
3 3
Output
4
Note

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