问题描述

给定一个正整数$m$，非负整数$a$（$0 \leq a < m$），以及一个正整数序列$A = (A_1, \ldots, A_N)$。

定义一个正整数集合$X$，满足$X = \{x>0 | x \equiv a \pmod{m}\}$。

Alice和Bob将轮流进行游戏。他们交替执行以下操作，其中Alice先开始：

• 选择一个索引$i$（$1 \leq i \leq N$）和一个正整数$x \in X$，使得$x \leq A_i$。将$A_i$更改为$A_i - x$。如果不存在这样的$(i, x)$，则当前玩家失败，游戏结束。

找出模$998244353$的数量，即Alice在第一轮可以选择的$(i, x)$对的数量，假设双方都以最优策略进行游戏。

约束条件

• $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$

输出

输出模$998244353$的数量，即Alice在第一轮可以选择的$(i, x)$对的数量，假设双方都以最优策略进行游戏。

样例输入1

3 1 0
5 6 7

样例输出1

3

我们有$X = \{1, 2, 3, 4, 5, \ldots\}$。满足条件的三个$(i,x)$对：$(1,4)$，$(2,4)$，$(3,4)$。

样例输入2

5 10 3
5 9 18 23 27

样例输出2

3

我们有$X = \{3, 13, 23, 33, 43, \ldots\}$。满足条件的三个$(i,x)$对：$(4,23)$，$(5,3)$，$(5,13)$。

样例输入3

4 10 8
100 101 102 103

样例输出3

0

即使Alice采取最优策略，她也无法获胜。因此，没有满足条件的$(i,x)$对。

样例输入4

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

样例输出4

943937640

满足条件的$833333333333334$个$(i,x)$对。输出计数模$998244353$。