Nastya received one more array on her birthday, this array can be used to play a traditional Byteland game on it. However, to play the game the players should first select such a subsegment of the array that $\frac{p}{s} = k$, where p is the product of all integers on the given array, s is their sum, and k is a given constant for all subsegments. 

Nastya wonders how many subsegments of the array fit the described conditions. A subsegment of an array is several consecutive integers of the array.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 2·10^5, 1 ≤ k ≤ 10^5), where n is the length of the array and k is the constant described above.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^8) — the elements of the array.


-----Output-----

In the only line print the number of subsegments such that the ratio between the product and the sum on them is equal to k.


-----Examples-----
Input
1 1
1

Output
1

Input
4 2
6 3 8 1

Output
2



-----Note-----

In the first example the only subsegment is [1]. The sum equals 1, the product equals 1, so it suits us because $\frac{1}{1} = 1$.

There are two suitable subsegments in the second example — [6, 3] and [3, 8, 1]. Subsegment [6, 3] has sum 9 and product 18, so it suits us because $\frac{18}{9} = 2$. Subsegment [3, 8, 1] has sum 12 and product 24, so it suits us because $\frac{24}{12} = 2$.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

[n, k] = list(map(int, input().strip().split()))
ais = list(map(int, input().strip().split()))

n1 = ais.count(1)

one_serie = [0 for _ in range(n)]
for i in reversed(list(range(n))):
	if ais[i] == 1:
		one_serie[i] = (0 if i == n - 1 else one_serie[i + 1]) + 1


n1_head = 0
count = 0

for i in range(n):
	p = 1
	s = 0
	if i > 0 and ais[i - 1] == 1:
		n1_head += 1
	n1_tail = n1 - n1_head
	j = i
	while j < n:
		if ais[j] == 1:
			if p % k == 0 and 1 <= p // k - s <= one_serie[j]:
				count += 1
			n1_tail -= one_serie[j]
			s += one_serie[j]
			j += one_serie[j]
		else:
			p *= ais[j]
			s += ais[j]
			if p == s * k:
				count += 1
			elif p > (s + n1_tail) * k:
				break
			j += 1

print (count)


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

ones_ser_ie = [0 for _ in range(n)]
cur_ones_ser_ie = 0
ones_in_tail_i = 0
for i in reversed(list(range(n))):
	if a[i] == 1:
		ones_in_tail_i += 1
		cur_ones_ser_ie += 1
	else:
		cur_ones_ser_ie = 0
	ones_ser_ie[i] = cur_ones_ser_ie


res = 0
for i in range(n):
	p = 1
	s = 0
	j = i
	ones_in_tail_j = ones_in_tail_i
	while j < n:
		if a[j] == 1:
			cur_ones_ser_ie = ones_ser_ie[j]
			if p % k == 0 and 1 <= p//k-s <= cur_ones_ser_ie:
				res += 1
			ones_in_tail_j -= cur_ones_ser_ie
			s += cur_ones_ser_ie
			j += cur_ones_ser_ie
		else:
			p *= a[j]
			s += a[j]
			if p == s * k:
				res += 1
			elif p > (s + ones_in_tail_j) * k:
				break
			j += 1
	if a[i] == 1:
		ones_in_tail_i -= 1
print(res)


from sys import stdin
import math
# stdin = open('in')

n, k = map(int, stdin.readline().split())
a = [int(x) for x in stdin.readline().split()]
nxt = [-1]*n
pref = []
f, s = -1, 0
for i in range(n):
	s += a[i]
	pref.append(s)
	nxt[n-1-i] = f
	if a[n-1-i] != 1:
		f = n-1-i
ans = 0
for i in range(n):
	pos, cur = i, 0
	prod = 1
	while 1:
		if prod > 1e18:
			break
		prod *= a[pos]
		cur += a[pos]
		if prod == k*cur:
			ans += 1
		nt = nxt[pos]
		if nt == -1:
			ones = n-1-pos
			if k*cur < prod and k*(cur+ones) >= prod:
				ans += 1
			break
		ones = nt - pos - 1
		if k*cur < prod and k*(cur+ones) >= prod and prod%k == 0:
			ans += 1
		cur += ones
		pos = nt
print(ans)

# https://codeforces.com/problemset/problem/992/D
n, k =  map(int, input().split())
a    =  list(map(int, input().split()))
max_ =  10 ** 13 + 1

def get(l, r, x):
    min_ =  min(l,r)
    max_ =  max(l,r)
    
    if x <= min_:
        return x + 1
    
    if x <= max_:
        return min_ + 1
    
    return l+r+1-x

def solve(a, k):
    cnt  = 0
    arr  = [i  for i, x in enumerate(a) if x>1]
    n_   = len(arr)
    
    for i in range(n_-1):
        curS = 0
        curP = 1 
        l    = arr[i] if i == 0 else arr[i] - arr[i-1] - 1 
        
        for j in range(i, n_):
            ind   = arr[j]
            curS += a[ind]
            curP *= a[ind]
        
            if curP > max_:
                break
            
            if curP % curS == 0:
                if curP // curS == k:
                    #print(arr[i], arr[j], curP, curS)
                    cnt+=1
                
            r = arr[j+1] - arr[j] - 1
            x = curP // k - curS
                
            if curP % k == 0 and x > 0  and x <= l + r:
                #print(arr[i], arr[j], curP, curS)
                cnt+=get(l, r, x)
            curS += r   
    
    if k==1:
        cnt+=len(a)-n_
    return cnt

ans=0
a.append(max_)
ans += solve(a, k)

print(ans)

n,k = map(int,input().split())
A = list(map(int,input().split()))
A = [0]+A;
x = 0
prev = [0 for i in range(n+1)]
sm = [0 for i in range(n+1)]
for i in range(1,n+1):
	prev[i] = x
	if A[i]>1:
		x = i
	sm[i] = A[i]+sm[i-1]
lim = int(2*(10**18))
ans = 0
for i in range(1,n+1):
	p = 1
	j = i
	while j:
		if lim//A[j]>p:
			s = sm[i]-sm[j-1]
			p *= A[j]
			if p%k == 0 and p//k>=s and j-1-prev[j]>=p/k-s:
				ans += 1
		else:
			break
		j = prev[j]
print(ans)

n,k = map(int,input().split())
A = list(map(int,input().split()))
A = [0]+A;
x = 0
prev = [0 for i in range(n+1)]
sm = [0 for i in range(n+1)]
for i in range(1,n+1):
	prev[i] = x
	if A[i]>1:
		x = i
	sm[i] = A[i]+sm[i-1]
lim = int(2*(10**18))
ans = 0
for i in range(1,n+1):
	p = 1
	j = i
	while j:
		if lim//A[j]>p:
			s = sm[i]-sm[j-1]
			p *= A[j]
			sx = s+j-1-prev[j]
			if p%k == 0 and p>=k*s and p<=k*sx:
				ans += 1
		else:
			break
		j = prev[j]
print(ans)