A - Meeting Division 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

1,2, \dots ,N の番号がついた N 個の会議があります。 会議 i の開始時刻は S_i、終了時刻は T_i です。

高橋君と青木君は、各会議に 2 人のうちちょうど一方を担当者として割り当てようとしています。 正の長さの時間帯で重なる 2 個の会議を同じ人が担当することはできません。 より厳密には、会議 i と会議 j を同じ人が担当することができるのは、T_i \le S_j または T_j \le S_i を満たすときに限ります。

条件を満たす担当者の割り当て方の個数を 998244353 で割った余りを求めてください。

制約

  • 1 \le N \le 3 \times 10^5
  • 1 \le S_i < T_i \le 2N
  • S_1,T_1,S_2,T_2,\dots,S_N,T_N は全て異なる
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 T_1
S_2 T_2
\vdots
S_N T_N

出力

条件を満たす担当者の割り当て方の個数を 998244353 で割った余りを出力せよ。

入力例 1

3
1 3
2 4
5 6

出力例 1

4

条件を満たす割り当て方は、以下の 4 通りです。

  • 高橋君が会議 1,3、青木君が会議 2 を担当する。
  • 高橋君が会議 1、青木君が会議 2,3 を担当する。
  • 高橋君が会議 2,3、青木君が会議 1 を担当する。
  • 高橋君が会議 2、青木君が会議 1,3 を担当する。

入力例 2

3
1 4
2 5
3 6

出力例 2

0

条件を満たす割り当て方は 0 通りです。

Score : 400 points

Problem Statement

There are N meetings numbered 1,2,\dots,N. Meeting i starts at time S_i and ends at time T_i.

Takahashi and Aoki are going to assign exactly one of themselves to each meeting as the person in charge. The same person cannot be in charge of two meetings that overlap for a positive length of time. More formally, the same person can be in charge of meetings i and j only if T_i \le S_j or T_j \le S_i.

Find the number, modulo 998244353, of ways to assign the people in charge that satisfy the conditions.

Constraints

  • 1 \le N \le 3 \times 10^5
  • 1 \le S_i < T_i \le 2N
  • S_1,T_1,S_2,T_2,\dots,S_N,T_N are all different.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
S_1 T_1
S_2 T_2
\vdots
S_N T_N

Output

Output the number, modulo 998244353, of ways to assign the people in charge that satisfy the conditions.

Sample Input 1

3
1 3
2 4
5 6

Sample Output 1

4

The following four assignments satisfy the conditions:

  • Takahashi is in charge of meetings 1,3, and Aoki is in charge of meeting 2.
  • Takahashi is in charge of meeting 1, and Aoki is in charge of meetings 2,3.
  • Takahashi is in charge of meetings 2,3, and Aoki is in charge of meeting 1.
  • Takahashi is in charge of meeting 2, and Aoki is in charge of meetings 1,3.

Sample Input 2

3
1 4
2 5
3 6

Sample Output 2

0

Zero assignments satisfy the conditions.