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.


-----Input-----

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 ≤ 10^5, 1 ≤ |k| ≤ 10).

Next line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — affection values of chemicals.


-----Output-----

Output a single integer — the number of valid segments.


-----Examples-----
Input
4 2
2 2 2 2

Output
8

Input
4 -3
3 -6 -3 12

Output
3



-----Note-----

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].

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Implementation

Complete search

Mathematics

Data structures


Solutions:
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
powers = set()
for i in range(0, 100):
	p = k ** i
	if abs(p) > 10 ** 9 * 10 ** 5:
		break
	else:
		powers.add(p)
s = [0]
for e in a:
	s.append(s[-1] + e)
result = 0
freq = {}
for i in range(0, n + 1):
	for p in powers:
		sx = s[i] - p
		if sx in freq:
			result += freq[sx]
	freq.setdefault(s[i], 0)
	freq[s[i]] += 1
print(result)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, K, A):
	presum = [0 for _ in range(N + 1)]
	vi = collections.defaultdict(list)
	for (i, v) in enumerate(A):
		presum[i + 1] = presum[i] + v
	for (i, v) in enumerate(presum):
		vi[v].append(i)
	maxval = max(presum)
	minval = min(presum)
	ans = 0
	for (i, v) in enumerate(presum):
		us = []
		if K > 1:
			c = 0
			u = v + 1
			while u <= maxval:
				us.append(u)
				c += 1
				u = v + K ** c
		elif K < -1:
			c = 0
			u = v + 1
			while u <= maxval:
				us.append(u)
				c += 2
				u = v + K ** c
			c = 1
			u = v + K
			while u >= minval:
				us.append(u)
				c += 2
				u = v + K ** c
		elif K == 1:
			us = [v + 1]
		elif K == -1:
			us = [v + 1, v - 1]
		for u in us:
			if u in vi:
				idx = vi[u]
				ans += len(idx) - bisect.bisect_right(idx, i)
	return ans
(N, K) = map(int, input().split())
A = [int(x) for x in input().split()]
print(solve(N, K, A))


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
s = [0 for i in range(n + 1)]
for i in range(n):
	s[i] = s[i - 1] + a[i]
ans = 0
bg = 1
can = set()
prev = dict()
prev[0] = 1
for i in range(50):
	can.add(bg)
	bg *= k
for i in range(n):
	for j in can:
		if s[i] - j in prev:
			ans += prev[s[i] - j]
	if s[i] in prev:
		prev[s[i]] += 1
	else:
		prev[s[i]] = 1
print(ans)


import sys
from itertools import accumulate

def solve():
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ps = [0] + list(accumulate(a))
	ap = {ps[n]: 1}
	ans = 0
	if k == 1:
		for i in range(n - 1, -1, -1):
			if ps[i] + 1 in ap:
				ans += ap[ps[i] + 1]
			if ps[i] in ap:
				ap[ps[i]] += 1
			else:
				ap[ps[i]] = 1
	elif k == -1:
		for i in range(n - 1, -1, -1):
			if ps[i] + 1 in ap:
				ans += ap[ps[i] + 1]
			if ps[i] - 1 in ap:
				ans += ap[ps[i] - 1]
			if ps[i] in ap:
				ap[ps[i]] += 1
			else:
				ap[ps[i]] = 1
	else:
		kp = [k ** i for i in range(50)]
		for i in range(n - 1, -1, -1):
			for kpi in kp:
				if ps[i] + kpi in ap:
					ans += ap[ps[i] + kpi]
			if ps[i] in ap:
				ap[ps[i]] += 1
			else:
				ap[ps[i]] = 1
	print(ans)

def __starting_point():
	solve()
__starting_point()


from itertools import accumulate, product
import math
R = lambda : map(int, input().split())
(n, k) = R()
(arr, acc) = (list(accumulate(R())), dict())
acc[0] = 1
res = 0
(rk, rks) = (1, [])
if abs(k) > 1:
	while rk < 10 ** 15:
		rks.append(rk)
		rk *= k
else:
	rks = [1] if k == 1 else [1, -1]
for x in arr:
	for rk in rks:
		res += acc.get(x - rk, 0)
	acc[x] = acc.get(x, 0) + 1
print(res)


from sys import stdin, stdout
(n, k) = map(int, stdin.readline().split())
values = list(map(int, stdin.readline().split()))
cnt = [0]
d = {0: 1}
power = [1]
ans = 0
if abs(k) > 1:
	while abs(power[-1]) < 10 ** 16:
		power.append(power[-1] * k)
elif k == -1:
	power = [1, -1]
elif not k:
	power = [0]
for i in range(n):
	cnt.append(cnt[-1] + values[i])
	if cnt[-1] in d:
		d[cnt[-1]] += 1
	else:
		d[cnt[-1]] = 1
	for v in power:
		if cnt[-1] - v in d:
			ans += d[cnt[-1] - v]
stdout.write(str(ans))


import math
import heapq

def main(arr, k):
	end = max(abs(sum([x for x in arr if x > 0])), abs(sum([x for x in arr if x < 0])))
	start = 1
	prefix = [arr[0]]
	cnt = {}
	for i in range(1, len(arr)):
		val = arr[i] + prefix[-1]
		prefix.append(val)
	ans = 0
	while start <= end:
		cnt = {}
		for i in range(len(prefix)):
			if prefix[i] - start in cnt:
				ans += cnt[prefix[i] - start]
			if prefix[i] == start:
				ans += 1
			if prefix[i] not in cnt:
				cnt[prefix[i]] = 0
			cnt[prefix[i]] += 1
		if k == 1:
			start = end + 1
		elif k == -1:
			if start == 1:
				start = -1
			else:
				break
		else:
			start *= k
	return ans
(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
print(main(arr, k))


(n, k) = list(map(int, input().split()))
A = list(map(int, input().split()))
cumsum = [0]
for a in A:
	cumsum.append(cumsum[-1] + a)
pows = set([k ** i for i in range(50)])
cum = dict({})
cum[0] = 1
res = 0
for x in cumsum[1:]:
	for pow in pows:
		if x - pow in cum:
			res += cum[x - pow]
	if x in cum:
		cum[x] += 1
	else:
		cum[x] = 1
print(res)


(n, k) = map(int, input().split())
ans = 0
a = list(map(int, input().split()))
b = set()
a = [0] + a
n += 1
for i in range(1, n):
	a[i] += a[i - 1]
t = 1
for z in range(100):
	if abs(t) <= 10 ** 16:
		b.add(t)
	t *= k
for x in b:
	d = dict()
	for i in a:
		ans += d.get(i - x, 0)
		d[i] = d.get(i, 0) + 1
print(ans)


f = lambda : map(int, input().split())
(n, k) = f()
t = {k ** i for i in range(48) if k ** i <= n * 1000000000.0}
s = y = 0
d = {0: 1}
for a in f():
	s += a
	d[s] = d.get(s, 0) + 1
	y += sum((d.get(s - x, 0) for x in t))
print(y)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
import inspect, re

def varname(p):
	for line in inspect.getframeinfo(inspect.currentframe().f_back)[3]:
		m = re.search('\\bvarname\\s*\\(\\s*([A-Za-z_][A-Za-z0-9_]*)\\s*\\)', line)
		if m:
			return m.group(1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	poss = []
	t = 1
	maxx = int(1e+19)
	if abs(k) > 1:
		while t < maxx:
			poss.append(t)
			t *= k
	elif k == 1:
		poss = [1]
	else:
		poss = [-1, 1]
	d = {0: 1}
	curr = 0
	ans = 0
	for i in range(n):
		curr += a[i]
		for j in poss:
			if -j + curr in d.keys():
				ans += d[-j + curr]
		if curr not in d.keys():
			d[curr] = 0
		d[curr] += 1
	print(ans)
	return
main()


from sys import stdin
(n, k) = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
sums = [0]
for x in arr:
	sums.append(sums[-1] + x)
powers = [1]
base = 1
if k != 1 and k != -1:
	while abs(base) <= 10 ** 14:
		base *= k
		powers.append(base)
if k == -1:
	powers.append(-1)
sums2 = {}
total = 0
for x in sums:
	for y in powers:
		if x - y in sums2:
			total += sums2[x - y]
	if x in sums2:
		sums2[x] += 1
	else:
		sums2[x] = 1
print(total)


N = 10 ** 14
(n, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
(t, res) = (0, 0)
d = {0: 1}
for i in arr:
	t += i
	res += d.get(t - 1, 0)
	i = k
	while i != 1 and -N <= i <= N:
		res += d.get(t - i, 0)
		i *= k
	d.setdefault(t, 0)
	d[t] += 1
print(res)


from sys import stdin
input = stdin.readline

def f(a, k):
	pref = 0
	ans = 0
	d = {0: 1}
	t = 1
	s = sum(a)
	fac = set([1])
	for i in range(50):
		t *= k
		fac.add(t)
	for i in a:
		pref += i
		for num in fac:
			need = pref - num
			ans += d.get(need, 0)
		d[pref] = d.get(pref, 0) + 1
	return ans
(n, k) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
print(f(a, k))


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
(n, k) = mints()
x = 1
pows = []
if k == 1:
	pows = [1]
elif k == -1:
	pows = [1, -1]
else:
	m = 10 ** (9 + 5)
	while x <= m:
		pows.append(x)
		x *= k
a = list(mints())
s = 0
z = dict()
z[0] = 1
r = 0
for i in range(n):
	s += a[i]
	z[s] = z.get(s, 0) + 1
	for j in pows:
		if s - j in z:
			r += z[s - j]
print(r)


from collections import defaultdict
from sys import stdin
(n, k) = [int(x) for x in input().split()]
a = []
l = stdin.readline()
b = l.split()
for i in b:
	a.append(int(i))
d = dict()
s = 0
cc = 10 ** 14 + 1
deg = set()
i = 0
if abs(k) != 1:
	while k ** i < cc:
		deg.add(k ** i)
		i += 1
elif k == -1:
	deg = {-1, 1}
else:
	deg = {1}
ans = 0
for i in range(n):
	s += a[i]
	for j in deg:
		if s - j in d:
			ans += d[s - j]
	if s in deg:
		ans += 1
	if s in d:
		d[s] += 1
	else:
		d[s] = 1
print(ans)


def ri():
	return map(int, input().split())
(n, k) = ri()
s = list(ri())
sd = dict()
for i in range(1, n):
	s[i] = s[i] + s[i - 1]
s.append(0)
ans = 0
pows = set([k ** i for i in range(50)])
for i in range(n - 1, -1, -1):
	if not s[i] in sd:
		sd[s[i]] = 1
	else:
		sd[s[i]] += 1
	for pow in pows:
		p = pow + s[i - 1]
		if p in sd:
			ans += sd[p]
print(ans)


(n, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
psum = [0]
d = {0: 1}
for i in range(n):
	num = psum[i] + arr[i]
	d.setdefault(num, 0)
	d[num] += 1
	psum.append(num)
if abs(k) == 1:
	e = d.copy()
	ans = 0
	for i in psum:
		e[i] -= 1
		if 1 + i in e:
			ans += e[1 + i]
	if k == -1:
		e = d.copy()
		for i in psum:
			e[i] -= 1
			if i - 1 in e:
				ans += e[i - 1]
	print(ans)
else:
	p = 0
	w = pow(k, p)
	ans = 0
	while w <= pow(10, 14):
		e = d.copy()
		for i in psum:
			e[i] -= 1
			if w + i in e:
				ans += e[w + i]
		p += 1
		w = pow(k, p)
	print(ans)


from math import log
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
(i, s) = (0, {})
if k == -1:
	s = {1: 0, -1: 0}
elif k == 1:
	s = {1: 0}
else:
	while max(-k ** i, k ** i) <= 10 ** 9 * n:
		s[k ** i] = 0
		i += 1
(d, p) = ({0: 1}, 0)
for i in a:
	p += i
	if p in d:
		d[p] += 1
	else:
		d[p] = 1
	for j in s:
		if p - j in d:
			s[j] += d[p - j]
r = 0
for i in s:
	r += s[i]
print(r)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 998244353
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	(n, k) = mi()
	a = li()
	x = [1, k]
	k1 = k
	for i in range(46):
		k1 *= k
		if k1 > 100000000000000.0 or k1 < -100000000000000.0:
			break
		x.append(k1)
	x = list(set(x))
	m = dd(int)
	m[0] = 1
	s = 0
	ans = 0
	for i in a:
		s += i
		for j in x:
			if s - j in m:
				ans += m[s - j]
		m[s] += 1
	print(ans)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


(n, k) = [int(x) for x in input().split()]
acc = 0
ans = 0
prefix = {0: 1}
for a in input().split():
	acc += int(a)
	ans += prefix.get(acc - 1, 0)
	i = k
	while i != 1 and i <= 10 ** 14 and (i >= -10 ** 14):
		ans += prefix.get(acc - i, 0)
		i *= k
	prefix.setdefault(acc, 0)
	prefix[acc] += 1
print(ans)


from collections import defaultdict
from sys import stdin
input = stdin.readline

def f(a, k):
	pref = 0
	ans = 0
	d = {0: 1}
	t = 1
	s = sum(a)
	fac = [1]
	if abs(k) > 1:
		for i in range(50):
			t *= k
			fac.append(t)
	if k == -1:
		fac.append(-1)
	for i in a:
		pref += i
		for num in fac:
			need = pref - num
			ans += d.get(need, 0)
		d[pref] = d.get(pref, 0) + 1
	return ans
(n, k) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
print(f(a, k))


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
N = 10 ** 14
cs = 0
ans = 0
d = {0: 1}
for i in range(n):
	cs += a[i]
	ans += d.get(cs - 1, 0)
	v = k
	while v != 1 and abs(v) <= N:
		ans += d.get(cs - v, 0)
		v *= k
	d.setdefault(cs, 0)
	d[cs] += 1
print(ans)


(n, k) = map(int, input().split())
powk = [k ** i for i in range(1, 60)]
a = list(map(int, input().split()))
s = 0
d = {0: 1}
ans = 0
INF = 10 ** 14
for i in range(n):
	s += a[i]
	if s - 1 in d:
		ans += d[s - 1]
	for j in range(len(powk)):
		q = powk[j]
		if q == 1:
			break
		if s - q in d:
			ans += d[s - q]
		if abs(j) > INF:
			break
	if s in d:
		d[s] += 1
	else:
		d[s] = 1
print(ans)


import sys
from itertools import accumulate

def solve():
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ps = [0] + list(accumulate(a))
	ap = {ps[n]: 1}
	ans = 0
	if k == 1:
		for i in range(n - 1, -1, -1):
			if ps[i] + 1 in ap:
				ans += ap[ps[i] + 1]
			if ps[i] in ap:
				ap[ps[i]] += 1
			else:
				ap[ps[i]] = 1
	elif k == -1:
		for i in range(n - 1, -1, -1):
			if ps[i] + 1 in ap:
				ans += ap[ps[i] + 1]
			if ps[i] - 1 in ap:
				ans += ap[ps[i] - 1]
			if ps[i] in ap:
				ap[ps[i]] += 1
			else:
				ap[ps[i]] = 1
	else:
		for i in range(n - 1, -1, -1):
			pk = 1
			while abs(pk) <= 10 ** 14:
				if ps[i] + pk in ap:
					ans += ap[ps[i] + pk]
				pk *= k
			if ps[i] in ap:
				ap[ps[i]] += 1
			else:
				ap[ps[i]] = 1
	print(ans)

def __starting_point():
	solve()
__starting_point()


import sys
from itertools import accumulate
from collections import Counter

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None

def solve():
	(n, k) = map(int, input().split())
	A = [int(i) for i in input().split()]
	cs = [0] + list(accumulate(A))
	S = Counter()
	ans = 0
	if k == 1:
		for i in range(n, -1, -1):
			if i == n:
				S[cs[i]] += 1
				continue
			if cs[i] + 1 in S:
				ans += S[cs[i] + 1]
			S[cs[i]] += 1
	elif k == -1:
		for i in range(n, -1, -1):
			if i == n:
				S[cs[i]] += 1
				continue
			if cs[i] + 1 in S:
				ans += S[cs[i] + 1]
			if cs[i] - 1 in S:
				ans += S[cs[i] - 1]
			S[cs[i]] += 1
	else:
		for i in range(n, -1, -1):
			if i == n:
				S[cs[i]] += 1
				continue
			w = 1
			while abs(w) < 10 ** 14 + 1:
				if cs[i] + w in S:
					ans += S[cs[i] + w]
				w *= k
			S[cs[i]] += 1
	print(ans)
solve()


from collections import defaultdict
(n, k) = map(int, input().split())
powers = set()
acc = 1
for i in range(61):
	powers.add(acc)
	acc *= k
data = list(map(int, input().split()))
prefix_sum = [0] * (n + 1)
for i in range(n):
	prefix_sum[i + 1] = prefix_sum[i] + data[i]
seen = {}
output = 0
for i in range(n + 1):
	for power in powers:
		if prefix_sum[i] - power in seen:
			output += seen[prefix_sum[i] - power]
	if prefix_sum[i] in seen:
		seen[prefix_sum[i]] += 1
	else:
		seen[prefix_sum[i]] = 1
print(output)


import os, io
from sys import stdout
import collections
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def powerOfK(k, max):
	if k == 1:
		return [1]
	if k == -1:
		return [-1, 1]
	result = []
	n = 1
	while n <= max:
		result.append(n)
		n *= k
	return result

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
ps = [0] + prefixSum(a)
can = set([])
canMap = collections.defaultdict(int)
powers = powerOfK(k, 10 ** 14)
result = 0
for e in ps:
	for p in powers:
		if e - p in can:
			result += canMap[e - p]
	can.add(e)
	canMap[e] += 1
print(result)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
p = a[:]
for i in range(1, n):
	p[i] += p[i - 1]
z = 1
o = 0
r = 50
if k == -1:
	r = 2
elif k == 1:
	r = 1
for i in range(r):
	d = {}
	for j in range(n):
		if p[j] not in d:
			d[p[j]] = 0
		d[p[j]] += 1
		if p[j] - z in d:
			o += d[p[j] - z]
		if p[j] - z == 0:
			o += 1
	z *= k
print(o)


(n, k) = input().split()
(n, k) = (int(n), int(k))
arr = input().split()
arr = [int(a) for a in arr]
su = {1}
for i in range(1, 100):
	if k ** i < 10 ** 10 * n:
		su.add(k ** i)
		continue
	break
d = {0: 1}
ans = 0
cumulative_sum = 0
for x in arr:
	cumulative_sum += x
	for s in su:
		if cumulative_sum - s in d:
			ans += d[cumulative_sum - s]
	d[cumulative_sum] = d.get(cumulative_sum, 0) + 1
print(ans)


(n, k) = map(int, input().split())
qw = [int(i) for i in input().split()]
q = 1
c = 0
for i in range(50):
	summ = 0
	er = {q: 1}
	for u in qw:
		summ += u
		if summ in er:
			c += er[summ]
		if summ + q in er:
			er[summ + q] += 1
		else:
			er[summ + q] = 1
	q *= k
if k == 1:
	print(c // 50)
elif k == -1:
	print(c // 25)
else:
	print(c)


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
ais = list(map(int, input().split()))
cc = collections.Counter()
MAX = 10 ** 5 * 10 ** 9
r = [1]
if abs(k) != 1:
	p = 1
	cur = k
	for _ in range(50):
		r.append(cur)
		cur *= k
r = set(r)
if k == -1:
	r.add(-1)
cc[0] += 1
cumul = 0
ans = 0
if len(ais) > 1:
	for j in range(len(ais)):
		cumul += ais[j]
		for y in r:
			if cumul - y in cc:
				ans += cc[cumul - y]
		cc[cumul] += 1
else:
	ans += 1 if ais[0] in r else 0
print(ans)


import sys
input = sys.stdin.readline
from collections import deque
(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
d = {}
d[0] = 1
c = 0
ans = 0
for i in range(n):
	c += a[i]
	if k == 1:
		if c - k in d:
			ans += d[c - k]
	elif k == -1:
		if c - 1 in d:
			ans += d[c - 1]
		if c + 1 in d:
			ans += d[c + 1]
	else:
		l = 1
		while l <= 10 ** 14 and l >= -10 ** 14:
			if c - l in d:
				ans += d[c - l]
			l *= k
	if c in d:
		d[c] += 1
	else:
		d[c] = 1
print(ans)


import math
(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if abs(k) > 1:
	valid = [k ** i for i in range(0, math.ceil(math.log(n * 1000000000.0) / math.log(abs(k))) + 1)]
elif k == -1:
	valid = [1, -1]
else:
	valid = [k]
s = 0
ans = 0
count = {s: 1}
for i in a:
	s += i
	for j in valid:
		if count.get(s - j):
			ans += count[s - j]
	if count.get(s):
		count[s] += 1
	else:
		count[s] = 1
print(ans)