Контролёр анализирует оборот магазина по дням. Известен массив из n чисел, где a_i — изменение оборота в i-й день. Также задан размер партии k.

Период с дня l по день r считается подходящим, если суммарный оборот за этот период кратен размеру партии, то есть сумма a_l + a_{l+1} + ... + a_r делится на k.

Требуется посчитать количество подходящих подотрезков.

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

Первая строка содержит два целых числа n и k — количество дней и размер партии.

Вторая строка содержит n целых чисел a_i — изменения оборота по дням.

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

Выведите одно число — количество подотрезков, сумма на которых кратна k.

Ответ может не помещаться в 32-битный целочисленный тип.

Ограничения

• 1 <= n <= 2 * 10^5
• 1 <= k <= 10^9
• |a_i| <= 10^9

Примеры

Пример 1

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

1 1
1

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

1

Пример 2

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

5 3
1 -1 2 -2 3

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

6

Пример 3

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

5 3
1 2 3 4 5

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

7