Problem Statement

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)$.

A set $X$ of positive integers is defined as $X = \\{x>0\\mid x\\equiv a \\pmod{m}\\}$.

Alice and Bob will play a game against each other. They will alternate turns performing the following operation, with Alice going first:

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

Find 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.

Constraints

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

---

Input

Input is given from Standard Input in the following format:

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

Output

Print 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.

---

Sample Input 1

3 1 0
5 6 7

Sample Output 1

3

We have $X = \\{1, 2, 3, 4, 5, \\ldots\\}$. Three pairs $(i,x)$ satisfy the condition: $(1,4)$, $(2,4)$, $(3,4)$.

---

Sample Input 2

5 10 3
5 9 18 23 27

Sample Output 2

3

We have $X = \\{3, 13, 23, 33, 43, \\ldots\\}$. Three pairs $(i,x)$ satisfy the condition: $(4,23)$, $(5,3)$, $(5,13)$.

---

Sample Input 3

4 10 8
100 101 102 103

Sample Output 3

0

Alice cannot win even if she plays optimally. Thus, zero pairs $(i,x)$ satisfy the condition.

---

Sample Input 4

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555

Sample Output 4

943937640

$833333333333334$ pairs $(i,x)$ satisfy the condition. Print the count modulo $998244353$.