E - Unfair Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

正整数 N,X,Y と長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。

N 個の袋があり、それぞれ袋 1 から袋 N までの番号が付けられています。袋 i にははじめ金貨が A_i 枚、銀貨が B_i 枚入っています。

この N 個の袋を使って高橋君と青木君がゲームをすることを考えます。最初に高橋君がいくつかの袋を取り（一つも取らなくても良い）、高橋君が取らなかった袋を全て青木君が取ります。その後、高橋君から始めて 2 人は交互に以下の操作を繰り返します。

  • 自分の持っている袋のうち金貨か銀貨が 1 枚以上入っている袋を選び、選んだ袋に対し以下の 2 つのうちいずれかを行う。
    • 金貨を 1 枚取り除き、銀貨を入れる。ただし、銀貨を入れる枚数は高橋君なら X 枚、青木君なら Y 枚である。この操作は金貨が選んだ袋に 1 枚以上ある場合にのみ行うことができる。
    • 銀貨を 1 枚取り除く。この操作は銀貨が選んだ袋に 1 枚以上ある場合にのみ行うことができる。
  • その後、選んだ袋を相手に渡す。

先に操作ができなくなったプレイヤーが負けとなります。

2 人が自分が勝つために最適な行動を取ったとき、高橋君が勝てるような最初の袋の取り方が何通りあるかを 998244353 で割ったあまりを求めてください。

制約

  • 1\le N\le 2\times 10^5
  • 1\le X,Y\le 10^9
  • 0\le A_i,B_i\le 10^9
  • 入力される値は全て整数

入力

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

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

2 人が自分が勝つために最適な行動をしたとしたとき、高橋君が勝てるような最初の袋の取り方が何通りあるかを 998244353 で割ったあまりを出力せよ。

入力例 1

2 1 1
1 0
1 1

出力例 1

2

高橋君が最初に袋 1,2 の両方を取った場合のゲームの進行の一例を示します。

  • 高橋君が袋 2 から金貨を 1 枚取り除き、銀貨を 1 枚入れる。その後、袋 2 を青木君に渡す。
    • 高橋君は金貨が 1 枚入った袋 1 を、青木君は銀貨が 2 枚入った袋 2 を持っている。
  • 青木君が袋 2 から銀貨を 1 枚取り除く。その後、袋 2 を高橋君に渡す。
    • 高橋君は金貨が 1 枚入った袋 1 と銀貨が 1 枚入った袋 2 を持っており、青木君は何も持っていない。
  • 高橋君が袋 1 から金貨を 1 枚取り除き、銀貨を 1 枚入れる。その後、袋 1 を青木君に渡す。
    • 高橋君は銀貨が 1 枚入った袋 2 を持っており、青木君は銀貨が 1 枚入った袋 1 を持っている。
  • 青木君が袋 1 から銀貨を 1 枚取り除く。その後、袋 1 を高橋君に渡す。
    • 高橋君は空の袋 1 と銀貨が 1 枚入った袋 2 を持っており、青木君は何も持っていない。
  • 高橋君が袋 2 から銀貨を 1 枚取り除く。その後、袋 2 を青木君に渡す。
    • 高橋君は空の袋 1 を持っており、青木君は空の袋 2 を持っている。
  • 青木君は操作ができないので、青木君の負けであり、高橋君の勝ちである。

高橋君は最初に取る袋が袋 2 のみであるか袋 1,2 の両方である場合にこのゲームに勝つことができます。したがって、 2 を出力してください。

入力例 2

2 2 1
1 2
1 2

出力例 2

3

高橋君は最初に袋 1,2 のどちらか、または両方取った場合にこのゲームに勝つことができます。

入力例 3

5 8 3
0 0
0 0
0 0
0 0
0 0

出力例 3

0

最初に高橋君がどのように袋を取っても高橋君は負けます。

入力例 4

7 2025 191
1323 9953
2763 3225
2624 5938
6718 2998
3741 7040
9837 1681
8817 4471

出力例 4

40

Score : 800 points

Problem Statement

You are given positive integers N, X, and Y, and two length-N sequences of non-negative integers A = (A_1,A_2,\ldots,A_N) and B = (B_1,B_2,\ldots,B_N).

There are N bags, numbered from 1 to N. Initially, bag i contains A_i gold coins and B_i silver coins.

Consider the following game played by Takahashi and Aoki using these N bags. First, Takahashi takes some of these bags (possibly zero), and Aoki takes all remaining bags. Then, starting with Takahashi, the two players alternate performing the following operation.

  • Choose one bag held by the player with at least one gold coin or silver coin in it, and do one of the following two actions for that bag.
    • Remove one gold coin and add silver coins; the number of silver coins to be added is X for Takahashi and Y for Aoki. This action can only be done if the chosen bag has at least one gold coin.
    • Remove one silver coin. This action can only be done if the chosen bag has at least one silver coin.
  • Then, give the chosen bag to the other player.

The player who cannot perform the operation loses the game.

Find the number, modulo 998244353, of ways Takahashi can initially take bags so that he will win under optimal play by both players.

Constraints

  • 1 \le N \le 2\times 10^5
  • 1 \le X, Y \le 10^9
  • 0 \le A_i, B_i \le 10^9
  • All input values are integers.

Input

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

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the number, modulo 998244353, of ways Takahashi can initially take bags so that he will win under optimal play by both players.

Sample Input 1

2 1 1
1 0
1 1

Sample Output 1

2

Consider the case where Takahashi initially takes bags 1 and 2. One possible progression of the game is as follows:

  1. Takahashi chooses bag 2, removes 1 gold coin, and adds 1 silver coin. Then, he gives bag 2 to Aoki.
    • Takahashi holds bag 1 with 1 gold coin. Aoki holds bag 2 with 2 silver coins.
  2. Aoki chooses bag 2 and removes 1 silver coin. Then, gives bag 2 to Takahashi.
    • Takahashi holds bags 1 with 1 gold coin and bag 2 with 1 silver coin. Aoki holds none.
  3. Takahashi chooses bag 1, removes 1 gold coin, and adds 1 silver coin. Then, he gives bag 1 to Aoki.
    • Takahashi holds bag 2 with 1 silver coin. Aoki holds bag 1 with 1 silver coin.
  4. Aoki chooses bag 1, removes 1 silver coin. Then, he gives bag 1 to Takahashi.
    • Takahashi holds bag 1 which is empty and bag 2 with 1 silver coin. Aoki holds none.
  5. Takahashi chooses bag 2 and removes 1 silver coin. Then, he gives bag 2 to Aoki.
    • Takahashi holds bag 1 which is empty. Aoki holds bag 2 which is empty.
  6. Aoki cannot perform the operation, so Aoki loses and Takahashi wins.

Takahashi can win if he initially takes only bag 2, or if he takes both bags 1 and 2. Therefore, the answer is 2.

Sample Input 2

2 2 1
1 2
1 2

Sample Output 2

3

Takahashi wins if he initially takes bag 1, bag 2, or both.

Sample Input 3

5 8 3
0 0
0 0
0 0
0 0
0 0

Sample Output 3

0

No matter how Takahashi chooses the bags initially, he will lose.

Sample Input 4

7 2025 191
1323 9953
2763 3225
2624 5938
6718 2998
3741 7040
9837 1681
8817 4471

Sample Output 4

40