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.