AT_arc191_e [ARC191E] Unfair Game

正整数 $ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ Y $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

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

### Sample Explanation 1 高橋君が最初に袋 $ 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 $ を出力してください。 ### Sample Explanation 2 高橋君は最初に袋 $ 1,2 $ のどちらか、または両方取った場合にこのゲームに勝つことができます。 ### Sample Explanation 3 最初に高橋君がどのように袋を取っても高橋君は負けます。 ### 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 $ - 入力される値は全て整数