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.