C. Химикаты Молли
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Молли Хупер есть n химикатов, расположенных в ряд. Каждый из химикатов имеет величину влиятельности, для химиката i эта величина равна ai.

Молли хочет, чтобы Шерлок в нее влюбился. Она собирается смешать все химикаты из некоторого отрезка так, чтобы сделать любовное зелье с величиной влиятельности, равной некоторой целой неотрицательной степени числа k. Величина влиятельности зелья равна сумме величин влиятельности химикатов на отрезке, из которого зелье составлено.

Помогите Молли найти количество отрезков, которые она может выбрать.

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

Первая строка содержит два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ |k| ≤ 10) — количество химикатов и число k, неотрицательной степенью которого должна быть величина влиятельности зелья.

Вторая строка содержит n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — величины влиятельности химикатов.

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

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

Примеры
Входные данные
4 2
2 2 2 2
Выходные данные
8
Входные данные
4 -3
3 -6 -3 12
Выходные данные
3
Примечание

Помните, что k0 = 1.

В первом примере Молли может получить следующие величины влиятельности:

  • 2: отрезки [1, 1], [2, 2], [3, 3], [4, 4];

  • 4: отрезки [1, 2], [2, 3], [3, 4];

  • 6: отрезки [1, 3], [2, 4];

  • 8: отрезки [1, 4].

Среди них величины 2, 4 и 8 являются степенями k = 2. Таким образом, ответ 8.

Во втором примере Молли может выбрать отрезки [1, 2], [3, 3], [3, 4].