#agc061c. [agc061_c]First Come First Serve

[agc061_c]First Come First Serve

Problem Statement

There are NN customers named 1,ldots,N1,\\ldots,N visiting a shop. Customer ii arrives at time AiA_i and leaves at time BiB_i. The queue order is first in-first out, so AiA_i are increasing, and BiB_i are increasing. Additionally, all AiA_i and BiB_i are pairwise distinct.

At the entrance there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo 998,244,353998\\,244\\,353.

Constraints

  • 1leqNleq5cdot1051 \\leq N \\leq 5 \\cdot 10^5
  • 1leqAi<Bileq2N1 \\leq A_i < B_i \\leq 2N
  • Ai<Ai+1A_i < A_{i + 1} (1leqileqN11 \\leq i \\leq N - 1)
  • Bi<Bi+1B_i < B_{i + 1} (1leqileqN11 \\leq i \\leq N - 1)
  • AineqBjA_i \\neq B_j (ineqji \\neq j)
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

NN A1A_1 B1B_1 vdots\\vdots ANA_N BNB_N

Output

Print the answer.


Sample Input 1

3
1 3
2 5
4 6

Sample Output 1

3

The possible orders are (1,2,3)(1, 2, 3), (2,1,3)(2, 1, 3), (1,3,2)(1, 3, 2).


Sample Input 2

4
1 2
3 4
5 6
7 8

Sample Output 2

1

The only possible order is (1,2,3,4)(1, 2, 3, 4).