配点 : $900$ 点

問題文

正整数 $m$, 非負整数 $a$ ($0\leq a < m$) および正整数列 $A = (A_1, \ldots, A_N)$ が与えられます．

正整数からなる集合 $X$ を $X = \{x>0\mid x\equiv a \pmod{m}\}$ により定めます．

先手太郎君と後手次郎君が対戦ゲームをします．ゲームでは先手太郎君の手番から始めて，交互に以下の操作を行います．

• 添字 $i$ ($1\leq i\leq N$) と正整数 $x\in X$ の組 $(i,x)$ であって，$x\leq A_i$ を満たすものをひとつ選ぶ．$A_i$ を $A_i - x$ に変更する．ただしそのような $(i, x)$ が存在しないならば，手番のプレイヤーの負けとしてゲームを終了する．

先手太郎君が最初の手番に選ぶことができる $(i, x)$ のうち，それ以降の手番で両者が最善を尽くした場合に先手太郎君が勝つことができるものの個数を $998244353$ で割った余りを答えてください．

制約

• $1\leq N\leq 3\times 10^5$
• $0\leq a < m\leq 10^9$
• $\max(1, a) \leq A_i\leq 10^{18}$

入力

入力は以下の形式で標準入力から与えられます．

$N$ $m$ $a$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

先手太郎君が最初の手番に選ぶことができる $(i, x)$ のうち，それ以降の手番で両者が最善を尽くした場合に先手太郎君が勝つことができるものの個数を $998244353$ で割った余りを出力してください．

3 1 0
5 6 7

3

$X = \{1, 2, 3, 4, 5, \ldots\}$ です．条件を満たす $(i,x)$ は $(1,4)$, $(2,4)$, $(3,4)$ の $3$ 個です．

5 10 3
5 9 18 23 27

3

$X = \{3, 13, 23, 33, 43, \ldots\}$ です．条件を満たす $(i,x)$ は $(4,23)$, $(5,3)$, $(5,13)$ の $3$ 個です．

4 10 8
100 101 102 103

0

先手太郎君は最善を尽くしても勝つことはできません．したがって条件を満たす $(i, x)$ は $0$ 個です．

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

943937640

条件を満たす $(i, x)$ は $833333333333334$ 個あります． $998244353$ で割った余りを出力してください．