You are given an array $A$ of size $N$, where the $i^{th}$ integer of the array is $A[i]$ and its value ranges between $1$ and $1000$ inclusive. You are required to complete the following task:

Assume that you are provided with $3$ additional numbers $K$, $X$, and $Y$. Your task is to report the number of unordered pairs of elements $(i,j)$ from this array, such that $(1 \le i < j \le N)$, $(A[i]+A[j]) \%K=X$, and $(A[i] \times A[j]) \%K=Y$.

Input format

• First line: Four space-separated integers $N$, $K$, $X$, and $Y$
• Next line: $N$ space-separated integers where the $i^{th}$ integer denotes $A[i]$

Output format

Print the required number of ordered pairs of array elements in a single line. As the answer could be rather large, be careful of integer overflows.

Constraints

$2 \le N \le 10^5$

$1 \le K \le 10^6$

$0 \le X , Y < K$

$1 \le A[i] \le 1000$