bazaT

Se dau $P$, $N$, $T$ și $C$ și un șir $a$ de $N$ numere naturale în baza 10: $a_1$, $a_2, \cdots, a_N$.

Un număr se numește $bazat$, dacă și numai dacă scris in baza $T$, ultima cifră a acestui număr este $C$.
Vom considera că cifrele în baza $T$ sunt $0$, $1$, $2, \cdots, T-2$, $T-1$. De exemplu cifrele în baza 15 sunt: 0, 1, 2, $\cdots$ 14.

De exemplu dacă $T$ = 6 și $C$ = 4: $4$, $10$, $70$ sunt $bazate$, deoarece numărul 4 transformat din baza 10 în baza 6 este 14, iar ultima cifră a acestuia este 4, numărul 10 transformat în baza 6 este 14, iar ultima cifră a lui 14 este 4, respectiv numărul 70, transformat în baza 6 este 154. Numerele $6$, $25$ și $44$ nu sunt $bazate$ deoarece $6$ = $10_6$ , $25$ = $41_6$ și $44 = 112_{6}$, acestea au ultima cifră diferită de 4.

Cerință

Dacă $P = 1$, aflați câte numere $bazate$ sunt în șir.

Dacă $P = 2$, aflați câte perechi ($i$, $j$) există astfel încat $1 \leq i < j \leq N$ și $a_i$ + $a_j$ este $bazat$.

Date de intrare

Pe prima linie a fișierului de intrare bazat.in se află patru numere naturale $P$, $N$, $T$ și $C$ separate printr-un spațiu. Pe cea de-a 2-a linie se află $N$ numere naturale separate prin câte un spațiu, reprezentând șirul $a$.

Date de ieșire

Pe prima linie din fișierul de ieșire bazat.out se află un număr natural reprezentând raspunsul la cerința $1$ dacă $P = 1$, altfel la cerința $2$.

Restricții și precizări

• $P = 1$ sau $P = 2$
• $1 \leq N \leq 100 \ 000$
• $2 \leq T$, $0 \leq C < T \leq 10^9$
• $0 \leq a_i \leq 10^9$, pentru oricare $1 \leq i \leq N$
• Pentru 30 de puncte $P = 1$
• Pentru 20 de puncte $P = 2$ și $N \leq 2 \ 000$
• Pentru 30 de puncte $P = 2$, $N > 2 \ 000$ și $T \leq 10^6$

Exemplul 1

bazat.in

1 7 6 4
10 154 6 25 94 44 70

bazat.out

4

Exemplul 2

bazat.in

2 7 6 2
10 154 6 25 94 44 70

bazat.out

7

Explicații

În primul exemplu, numerele $bazate$ sunt $10, 154, 94, 70$.

În al doilea exemplu, perechile ($i$, $j$) sunt { ($1$, $2$); ($1$, $5$); ($1$, $7$); ($2$, $5$); ($2$, $7$); ($3$, $6$); ($5$, $7$)}.

Acestea corespund sumelor {$164$, $104$, $80$, $248$, $224$, $50$, $164$} .