{"problem":{"name":"Unfair Game","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc191_e"},"statements":[{"statement_type":"Markdown","content":"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)$.\nThere are $N$ bags, numbered from $1$ to $N$. Initially, bag $i$ contains $A_i$ gold coins and $B_i$ silver coins.\nConsider 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.\n\n*   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.\n    *   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.\n    *   Remove one silver coin. This action can only be done if the chosen bag has at least one silver coin.\n*   Then, give the chosen bag to the other player.\n\nThe player who cannot perform the operation loses the game.\nFind the number, modulo $998244353$, of ways Takahashi can initially take bags so that he will win under optimal play by both players.\n\n## Constraints\n\n*   $1 \\le N \\le 2\\times 10^5$\n*   $1 \\le X, Y \\le 10^9$\n*   $0 \\le A_i, B_i \\le 10^9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $X$ $Y$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc191_e","tags":[],"sample_group":[["2 1 1\n1 0\n1 1","2\n\nConsider the case where Takahashi initially takes bags $1$ and $2$. One possible progression of the game is as follows:\n\n1.  Takahashi chooses bag $2$, removes $1$ gold coin, and adds $1$ silver coin. Then, he gives bag $2$ to Aoki.\n    *   Takahashi holds bag $1$ with $1$ gold coin. Aoki holds bag $2$ with $2$ silver coins.\n2.  Aoki chooses bag $2$ and removes $1$ silver coin. Then, gives bag $2$ to Takahashi.\n    *   Takahashi holds bags $1$ with $1$ gold coin and bag $2$ with $1$ silver coin. Aoki holds none.\n3.  Takahashi chooses bag $1$, removes $1$ gold coin, and adds $1$ silver coin. Then, he gives bag $1$ to Aoki.\n    *   Takahashi holds bag $2$ with $1$ silver coin. Aoki holds bag $1$ with $1$ silver coin.\n4.  Aoki chooses bag $1$, removes $1$ silver coin. Then, he gives bag $1$ to Takahashi.\n    *   Takahashi holds bag $1$ which is empty and bag $2$ with $1$ silver coin. Aoki holds none.\n5.  Takahashi chooses bag $2$ and removes $1$ silver coin. Then, he gives bag $2$ to Aoki.\n    *   Takahashi holds bag $1$ which is empty. Aoki holds bag $2$ which is empty.\n6.  Aoki cannot perform the operation, so Aoki loses and Takahashi wins.\n\nTakahashi can win if he initially takes only bag $2$, or if he takes both bags $1$ and $2$. Therefore, the answer is $2$."],["2 2 1\n1 2\n1 2","3\n\nTakahashi wins if he initially takes bag $1$, bag $2$, or both."],["5 8 3\n0 0\n0 0\n0 0\n0 0\n0 0","0\n\nNo matter how Takahashi chooses the bags initially, he will lose."],["7 2025 191\n1323 9953\n2763 3225\n2624 5938\n6718 2998\n3741 7040\n9837 1681\n8817 4471","40"]],"created_at":"2026-03-03 11:01:13"}}