Background

LMX and HQZ are studying how to partition points.

Problem Description

Given $n$ points, each point provides a pair of constraints $l_i, r_i (0 \le l_i < i < r_i \le n+1)$. A partition is defined to be good if and only if, for every point $i$, after partitioning, both $l_i$ and $r_i$ are not in the same interval as $i$. Find the number of good partitions. Output the answer modulo $998244353$.

Supplement: In this problem, a partition means dividing the $n$ points into several intervals such that each point belongs to exactly one interval. $l_i = 0$ and $r_i = n+1$ can be considered as no constraint.

Input Format

The first line contains an integer $n$, which represents the number of points.

The next $n$ lines each contain two integers $l_i, r_i$ on the $i$-th line.

Output Format

Output one integer on the first line, which is the answer modulo $998244353$.

5
0 3
0 3
1 6
2 6
2 6

8

Hint

Sample Explanation #1

The $8$ legal interval partitions in the sample are:

$[1,2],[3,5]$

$[1,1],[2,2],[3,5]$

$[1,2],[3,3],[4,5]$

$[1,1],[2,2],[3,3],[4,5]$

$[1,2],[3,4],[5,5]$

$[1,1],[2,2],[3,4],[5,5]$

$[1,2],[3,3],[4,4],[5,5]$

$[1,1],[2,2],[3,3],[4,4],[5,5]$

For all testdata, $1 \le n \le 2 \times 10^6$, $0 \le l_i < i < r_i \le n+1$.

Translated by ChatGPT 5