题目描述

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

定义一个正整数集合 $X$，这个集合中的元素满足 $x > 0$ 且 $x \equiv a \pmod{m}$。

在这个游戏中，先手玩家太郎君和后手玩家次郎君轮流操作。游戏从太郎君开始进行，操作如下：

• 选择一个下标 $i$（$1 \le i \le N$）和一个正整数 $x \in X$ 的组合 $(i, x)$，要求 $x \le A_i$。然后将 $A_i$ 更改为 $A_i - x$。如果找不到符合条件的 $(i, x)$ 组合，当前回合的玩家即输掉游戏。

你的任务是计算，在太郎君第一次操作中，能够选择的所有组合 $(i, x)$ 中，经双方均采取最佳策略后，能让太郎君赢得游戏的组合数量。请输出该数量对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入给出：

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

输出格式

输出满足条件的首回合组合数对 $998244353$ 取模的结果。

样例 1

输入

3 1 0
5 6 7

输出

3

样例 2

输入

5 10 3
5 9 18 23 27

输出

3

样例 3

输入

4 10 8
100 101 102 103

输出

0

样例 4

输入

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

输出

943937640

说明/提示

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

示例解释 1

集合 $X = \{1, 2, 3, 4, 5, \ldots\}$。符合条件的组合有 $(1, 4)$, $(2, 4)$, $(3, 4)$，共 $3$ 个。

示例解释 2

集合 $X = \{3, 13, 23, 33, 43, \ldots\}$。符合条件的组合有 $(4, 23)$, $(5, 3)$, $(5, 13)$，共 $3$ 个。

示例解释 3

太郎君无论如何都无法赢得比赛，因此，符合条件的组合是 $0$ 个。

示例解释 4

符合条件的组合有 $833333333333334$ 个，输出其对 $998244353$ 取模的结果。

本翻译由 AI 自动生成