Даны $n$ целых чисел $a_1, \dots, a_n$ и модуль $M = 10^K - 1$. Найдите количество всех троек $(i, j, k)$ таких, что $1 \le i \le j \le k \le n$ и $a_i + a_j + a_k \equiv 0 \pmod M$.

Входные данные

В первой строке входных данных содержатся два целых числа $n$ и $K$ ($1 \le n \le 500$, $1 \le K \le 2 \times 10^4$).

В каждой из следующих $n$ строк содержится одно целое число $a_i$. Гарантируется, что $0 \le a_i < 10^{20\,000}$.

Выходные данные

Выведите единственное целое число — количество таких троек.

Примеры

Входные данные 1

4 1
0
1
10
17

Выходные данные 1

3