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 \)