{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $m$, a non-negative integer $a$ ($0\\leq a < m$), and a sequence of positive integers $A = (A_1, \\ldots, A_N)$.\nA set $X$ of positive integers is defined as $X = {x>0\\mid x\\equiv a \\pmod{m}}$.\nAlice and Bob will play a game against each other. They will alternate turns performing the following operation, with Alice going first:\n\n*   Choose a pair $(i,x)$ of an index $i$ ($1\\leq i\\leq N$) and a positite integer $x\\in X$ such that $x\\leq A_i$. Change $A_i$ to $A_i - x$. If there is no such $(i, x)$, the current player loses and the game ends.\n\nFind the number, modulo $998244353$, of pairs $(i, x)$ that Alice can choose in her first turn so that she wins if both players play optimally in subsequent turns."},{"iden":"constraints","content":"*   $1\\leq N\\leq 3\\times 10^5$\n*   $0\\leq a < m\\leq 10^9$\n*   $\\max(1, a) \\leq A_i\\leq 10^{18}$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $m$ $a$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"3 1 0\n5 6 7"},{"iden":"sample output 1","content":"3\n\nWe have $X = {1, 2, 3, 4, 5, \\ldots}$. Three pairs $(i,x)$ satisfy the condition: $(1,4)$, $(2,4)$, $(3,4)$."},{"iden":"sample input 2","content":"5 10 3\n5 9 18 23 27"},{"iden":"sample output 2","content":"3\n\nWe have $X = {3, 13, 23, 33, 43, \\ldots}$. Three pairs $(i,x)$ satisfy the condition: $(4,23)$, $(5,3)$, $(5,13)$."},{"iden":"sample input 3","content":"4 10 8\n100 101 102 103"},{"iden":"sample output 3","content":"0\n\nAlice cannot win even if she plays optimally. Thus, zero pairs $(i,x)$ satisfy the condition."},{"iden":"sample input 4","content":"5 2 1\n111111111111111 222222222222222 333333333333333 444444444444444 555555555555555"},{"iden":"sample output 4","content":"943937640\n\n$833333333333334$ pairs $(i,x)$ satisfy the condition. Print the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}