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.

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.

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

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.

见题面 Input 部分

见题面 Output 部分