Connected Interval Prefixes - Repovive Standard Round 5 | Repovive

14F. Connected Interval Prefixes

3000 pts1s256 MB

You are given $n$ closed intervals on the real line. The endpoints of every interval are integers between $1$ and $n$ .

A permutation $p_1, p_2, \ldots, p_n$ of the intervals is called good if for every $k$ with $1 \le k \le n$ , the union of intervals $p_1, p_2, \ldots, p_k$ is connected.

Equivalently, for every prefix, the union must be a single closed interval on the real line.

For each test case, count the number of good permutations modulo $998244353$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 3000$
The sum of $n^2$ over all test cases is at most $9 \times 10^6$ .
$1 \le l_i \le r_i \le n$

Input

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
1 1

Case 2

2
1 1
2 2

Case 3

Case 4

Case 5

Explanation

Case 1

There is only one interval, so the only permutation is good.

Case 2

After both intervals are chosen, the union contains two separate points and is not connected. Therefore no permutation is good.

Case 3

Every two intervals intersect, so any order keeps every prefix connected. There are $3! = 6$ good permutations.

Case 4

If $[1,3]$ is first, the other two intervals can be placed in any order. If a single-point interval is first, $[1,3]$ must be second. This gives $2 + 1 + 1 = 4$ good permutations.

Case 5

There are $4! = 24$ permutations in total. The only bad ones are the four permutations where $[1,2]$ and $[3,4]$ are the first two intervals in either order, because the second prefix is disconnected. So the answer is $20$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given $n$ closed intervals on the real line. The endpoints of every interval are integers between $1$ and $n$ .

A permutation $p_1, p_2, \ldots, p_n$ of the intervals is called good if for every $k$ with $1 \le k \le n$ , the union of intervals $p_1, p_2, \ldots, p_k$ is connected.

Equivalently, for every prefix, the union must be a single closed interval on the real line.

For each test case, count the number of good permutations modulo $998244353$ .

$1 \le t \le 100$
$1 \le n \le 3000$
The sum of $n^2$ over all test cases is at most $9 \times 10^6$ .
$1 \le l_i \le r_i \le n$

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Every two intervals intersect, so any order keeps every prefix connected. There are $3! = 6$ good permutations.

If $[1,3]$ is first, the other two intervals can be placed in any order. If a single-point interval is first, $[1,3]$ must be second. This gives $2 + 1 + 1 = 4$ good permutations.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

14F. Connected Interval Prefixes

Constraints

Input

Output

Samples

14F. Connected Interval Prefixes

Constraints

Input

Output

Samples