P10807 [LMXOI Round 2] Disaster

LMX and HQZ are studying how to partition points.

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.

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 one integer on the first line, which is the answer modulo $998244353$.

**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$. | Subtask ID | $n$ | Special Property | Score | | :--------: | :----------------: | :--------------: | :---: | | Subtask #1 | $\le 20$ | None | $5$ | | Subtask #2 | $\le 500$ | None | $10$ | | Subtask #3 | $\le 5000$ | None | $20$ | | Subtask #4 | $\le 5 \times 10^5$ | $l_i = 0$ | $10$ | | Subtask #5 | $\le 5 \times 10^5$ | None | $25$ | | Subtask #6 | $\le 2 \times 10^6$ | None | $30$ | Translated by ChatGPT 5