E - Team Division 解説 /

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

配点 : 475 点

問題文

選手 1、選手 2、\ldots、選手 N の N 人を、次の条件をすべてみたすように 2 つの（区別できる）チーム A,B に分けます。

  • それぞれのチームは 1 人以上の選手からなる。
  • それぞれの選手はチーム A,B のちょうど一方に属する。
  • 選手 i が所属するチームに属する人数は L_i 人以上 R_i 人以下である。

条件をみたすような分け方は何通りあるか求め、その値を 998244353 で割ったあまりを出力してください。
ただし、2 つの分け方が異なるとは、ある選手が存在してその選手の属するチームが異なることをさします。

制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq L_i\leq R_i\leq N-1
  • 入力はすべて整数

入力

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

条件をみたす分け方の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

3
1 1
1 2
2 2

出力例 1

2

次の 2 通りの分け方が条件をみたします。

  • 選手 1: チーム A, 選手 2: チーム B, 選手 3: チーム B
  • 選手 1: チーム B, 選手 2: チーム A, 選手 3: チーム A

2 を 998244353 で割ったあまりは 2 であるため、2 を出力します。

入力例 2

6
1 5
1 5
2 5
1 3
3 5
2 5

出力例 2

30

条件をみたす分け方は 30 通りあります。

Score : 475 points

Problem Statement

Divide N players, player 1, player 2, \ldots, player N, into two (distinguishable) teams A and B satisfying all of the following conditions.

  • Each team consists of at least one player.
  • Each player belongs to either team A or team B, but not both.
  • The number of players in the team that player i belongs to is at least L_i and at most R_i.

Find the number of ways to divide the players satisfying the conditions, and output the count modulo 998244353.
Two divisions are considered different if there exists a player who belongs to different teams in the two divisions.

Constraints

  • 2\leq N\leq 2\times 10^5
  • 1\leq L_i\leq R_i\leq N-1
  • All input values are integers.

Input

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Output the number of valid divisions, modulo 998244353.

Sample Input 1

3
1 1
1 2
2 2

Sample Output 1

2

The following two divisions satisfy the conditions.

  • Player 1: Team A, Player 2: Team B, Player 3: Team B
  • Player 1: Team B, Player 2: Team A, Player 3: Team A

Since 2 modulo 998244353 is 2, output 2.

Sample Input 2

6
1 5
1 5
2 5
1 3
3 5
2 5

Sample Output 2

30

There are 30 valid divisions.