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

Difficulty: competition

Starter code:

Solutions:
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
cumsum = [0]

for a in A:
   cumsum.append(cumsum[-1] + a)
#print(cumsum)
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)


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))

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)


n, k = map(int, input().split())
A = list(map(int, input().split()))
cumsum = [0]

for a in A:
   cumsum.append(cumsum[-1] + a)
#print(cumsum)
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)

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 * 1e9) / math.log(abs(k))) + 1)]
elif k == -1:
    valid = [1, -1]
else:
    valid = [k]
# print(math.log(n * 1e9) / math.log(abs(k)))
# print(valid)

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)


n, k = list(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:
        # s[i] - s[x] == p
        sx = s[i] - p
        if sx in freq:
            result += freq[sx]
    freq.setdefault(s[i], 0)
    freq[s[i]] += 1

print(result)


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
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)


def __starting_point():
    solve()
__starting_point()

#!/usr/bin/env python3
#from collections import defaultdict

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)

#!/usr/bin/env python3
#from collections import defaultdict

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)

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

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()

f = lambda: map(int, input().split())
n, k = f()
t = {k ** i for i in range(48) if k ** i <= n * 1e9}
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)

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)

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

#print(su)
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)

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)

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
cumsum = [0]

for a in A:
   cumsum.append(cumsum[-1] + a)
#print(cumsum)
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)




# Made By Mostafa_Khaled


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)

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)

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)

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)

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)

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/10/20

"""

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:
            # even
            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 = [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)