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: HARD
Tags: Mathematics

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
[n, k] = 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(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) = 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:
					cnt += 1
			r = arr[j + 1] - arr[j] - 1
			x = curP // k - curS
			if curP % k == 0 and x > 0 and (x <= l + r):
				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)


from sys import stdin
import math
(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 > 1e+18:
			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)


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


(n, k) = map(int, input().split())
v = list(map(int, input().split()))
(pos, pref) = ([-1], [])
ans = 0
for i in range(n):
	if v[i] != 1:
		pos.append(i)
	if v[i] == 1 and k == 1:
		ans += 1
	if i:
		pref.append(pref[-1] + v[i])
	else:
		pref.append(v[i])
pos.append(n)
m = len(pos)
inf = int(2e+18 + 10)
for i in range(1, m - 1):
	p = 1
	for j in range(i, m - 1):
		p = p * v[pos[j]]
		if p > inf:
			break
		s = pref[pos[j]]
		if pos[i]:
			s -= pref[pos[i] - 1]
		if s * k == p:
			ans += 1
		d = p - s * k
		if d > 0 and d % k == 0:
			w = d // k
			f = min(pos[i] - pos[i - 1] - 1, w)
			b = min(pos[j + 1] - pos[j] - 1, w)
			if f + b < w:
				continue
			ans += f + b - w + 1
print(ans)


(n, k) = map(int, input().split())
flag = [0 for i in range(0, n)]
a = list(map(int, input().split()))
r = [-1 for i in range(0, n)]
i = 0
while i < n:
	if a[i] != 1:
		i = i + 1
		continue
	j = i
	while j < n and a[j] == 1:
		j = j + 1
	while i < j:
		r[i] = j - 1
		i = i + 1
ans = 0
maxn = 2 ** 63 - 1
for i in range(0, n):
	p = 1
	s = 0
	j = i
	while j < n:
		if a[j] != 1:
			p = p * a[j]
			s = s + a[j]
			if p % s == 0 and p // s == k:
				ans = ans + 1
			j = j + 1
		else:
			if p % k == 0 and (p // k - s > 0 and p // k - s <= r[j] - j + 1):
				ans = ans + 1
			s = s + r[j] - j + 1
			j = r[j] + 1
		if p >= maxn:
			break
print(ans)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
from itertools import accumulate
C = [0] + A
C = list(accumulate(C))
A = [0] + A
P = [0] * (n + 1)
x = 0
for i in range(1, n + 1):
	P[i] = x
	if A[i] > 1:
		x = i
INF = 2 * 10 ** 18 + 1
ans = 0
for i in range(1, n + 1):
	p = 1
	j = i
	while j:
		if p * A[j] < INF:
			s = C[i] - C[j - 1]
			p *= A[j]
			if p % k == 0:
				d = p // k - s
				if 0 <= d <= j - P[j] - 1:
					ans += 1
		else:
			break
		j = P[j]
print(ans)


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