题目描述

正整数 $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$ で割った余りを答えてください．

输入格式

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

$N$ $m$ $a$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

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

3 1 0
5 6 7

3

5 10 3
5 9 18 23 27

3

4 10 8
100 101 102 103

0

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

943937640

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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