Contest Duration: - (local time) (120 minutes) Back to Home
F - Arithmetic Sequence Nim /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 添字 i (1\leq i\leq N) と正整数 x\in X の組 (i,x) であって，x\leq A_i を満たすものをひとつ選ぶ．A_iA_i - x に変更する．ただしそのような (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


### 入力例 1

3 1 0
5 6 7


### 出力例 1

3


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

### 入力例 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 個です．

### 入力例 3

4 10 8
100 101 102 103


### 出力例 3

0


### 入力例 4

5 2 1
111111111111111 222222222222222 333333333333333 444444444444444 555555555555555


### 出力例 4

943937640


Score : 900 points

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