secvk

Cerință

Se dă un vector cu $N$ elemente naturale $a_1, a_2, ..., a_N$ și un număr natural nenul $K$. Să se determine numărul de subsecvențe ale vectorului care au suma elementelor divizibilă cu $K$.
O subsecvență este o mulțime de elemente consecutive din vectorul dat.

Date de intrare

Pe prima linie se află numerele $N$ și $K$, cu semnificația din enunț.
Pe a doua linie se găsesc elementele vectorului dat, $a_1, a_2, ..., a_N$, separate prin spațiu.

Date de ieșire

Pe prima linie se va afla numărul de subsecvențe care au suma elementelor divizibilă cu $K$.

Restricții și precizări

• $1 \leq N, K \leq 1 \ 000$;
• $0 \leq a_i \leq 10^9$.

Exemplul 1

stdin

2 1
3 5

stdout

3

Explicație

Există $3$ subsecvențe care au suma elementelor divizibilă cu $K = 1$: $\{3\}, \{5\}, \{3, 5\}$, căci numerele $3, 5$ și $8$ sunt divizibile cu $1$.

Exemplul 2

stdin

2 2
0 1

stdout

1

Explicație

Singura subsecvență care are suma elementelor divizibilă cu $K = 2$ este $\{0\}$, căci $0$ este divizibil cu $2$.