CF776C.Molly's Chemicals

Molly Hooper has n different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The i-th of them has affection value a__i.

Molly wants Sherlock to fall in love with her. She intends to do this by mixing a contiguous segment of chemicals together to make a love potion with total affection value as a non-negative integer power of k. Total affection value of a continuous segment of chemicals is the sum of affection values of each chemical in that segment.

Help her to do so in finding the total number of such segments.

莫莉·胡珀将 $n$ 种不同的化学药品排成一行。每种化学药品都有一个“好感值”，其中第 $i$ 种药品的好感值为 $a_i$。

莫莉希望夏洛克爱上她。她计划通过混合一段连续的化学药品来配制一种“爱情魔药”，使得该魔药的总好感值恰好为 $k$ 的某个非负整数次幂（即形如 $k^p$，其中 $p$ 为非负整数）。一段连续化学药品段的总好感值，等于该段中所有化学药品好感值之和。

请帮她计算：满足上述条件的连续子段共有多少个？

The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection value is a non-negative power of this number k. (1 ≤ n ≤ 105, 1 ≤ |k| ≤ 10).

Next line contains n integers _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109) — affection values of chemicals.

输入的第一行包含两个整数 $n$ 和 $k$，分别表示化学药品的数量，以及使得总好感值为该数 $k$ 的一个非负整数次幂的数。（$1 \leq n \leq 10^5$，$1 \leq |k| \leq 10$）

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$-10^9 \leq a_i \leq 10^9$）—— 各化学药品的好感值。

Output a single integer — the number of valid segments.

输出一个整数——有效区间的数量。

Do keep in mind that _k_0 = 1.

In the first sample, Molly can get following different affection values:

• 2: segments [1, 1], [2, 2], [3, 3], [4, 4];

• 4: segments [1, 2], [2, 3], [3, 4];

• 6: segments [1, 3], [2, 4];

• 8: segments [1, 4].

Out of these, 2, 4 and 8 are powers of k = 2. Therefore, the answer is 8.

In the second sample, Molly can choose segments [1, 2], [3, 3], [3, 4].

请注意，$k_0 = 1$。

在第一个样例中，Molly 可以得到以下不同的好感值：

• $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$。

在第二个样例中，Molly 可以选择子段 $[1, 2]$、$[3, 3]$、$[3, 4]$。