Counting Good Partitions

You are given n points numbered from 1 to n. For each point i, a restriction pair \( (l_i, r_i) \) is provided satisfying \(0 \le l_i < i < r_i \le n+1\). A partition of the points into contiguous intervals is called good if for every point \( i \) that lies in an interval \([L, R]\), the following conditions hold:

• If \(l_i \neq 0\) (i.e. there is a restriction on the left), then \(L > l_i\).
• If \(r_i \neq n+1\) (i.e. there is a restriction on the right), then \(R < r_i\).

Here, a partition means dividing the sequence of points \(1, 2, \dots, n\) into one or more contiguous intervals so that each point lies in exactly one interval. Note that when \(l_i = 0\) or \(r_i = n+1\), the corresponding side is unrestricted.

Your task is to compute the number of good partitions modulo \(998244353\).

Example Explanation: Consider a case with \( n = 3 \) and the following restrictions:

• Point 1: \(l_1 = 0,\ r_1 = 4\)
• Point 2: \(l_2 = 0,\ r_2 = 4\)
• Point 3: \(l_3 = 1,\ r_3 = 4\)

The valid partitions can be determined by checking the conditions for each interval. In this example, there are 3 good partitions.

inputFormat

The input consists of:

1. The first line contains a single integer \(n\) representing the number of points.
2. The next \(n\) lines each contain two integers \(l_i\) and \(r_i\) separated by a space, representing the restrictions for the i-th point. It is guaranteed that \(0 \le l_i < i < r_i \le n+1\).

outputFormat

Output a single integer, the number of good partitions modulo \(998244353\).

sample

3
0 4
0 4
1 4

3