Mając dane $N$ liczb całkowitych $a_1, \dots, a_N$ oraz moduł $M = 10^K - 1$, znajdź liczbę wszystkich trójek $(i, j, k)$ takich, że $1 \le i \le j \le k \le N$ oraz $a_i + a_j + a_k \equiv 0 \pmod M$.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite $N$ oraz $K$ ($1 \le N \le 500$, $1 \le K \le 2 \times 10^4$).

Każda z kolejnych $N$ linii zawiera jedną liczbę całkowitą $a_i$. Gwarantuje się, że $0 \le a_i < 10^{20 000}$.

Wyjście

Wypisz w jednej linii pojedynczą liczbę całkowitą, oznaczającą liczbę takich trójek.

Przykład

Wejście

4 1
0
1
10
17

Wyjście

3