You have a string of decimal digits s. Let's define bij = si·sj. Find in matrix b the number of such rectangles that the sum bij for all cells (i, j) that are the elements of the rectangle equals a in each rectangle.

A rectangle in a matrix is a group of four integers (x, y, z, t) (x ≤ y, z ≤ t). The elements of the rectangle are all cells (i, j) such that x ≤ i ≤ y, z ≤ j ≤ t.

Input

The first line contains integer a (0 ≤ a ≤ 109), the second line contains a string of decimal integers s (1 ≤ |s| ≤ 4000).

Output

Print a single integer — the answer to a problem.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

10
12345


Output

6


Input

16
439873893693495623498263984765


Output

40
from collections import Counter
if __name__ == '__main__':
	a = int(input())
	seq = list(input())
	n = len(seq)
	seq = [int(x) for x in seq]

	curr_sum = 0
	cum_sum = [0]
	sum_pairs = list()

	for i in seq:
		curr_sum += i
		cum_sum.append(curr_sum)
	for i in range(1, n+1):
		for j in range(i, n+1):
			if i <= j:
				sum_pairs.append(cum_sum[j]-cum_sum[i-1])

	freq = Counter(sum_pairs)

	unique_sum = freq.keys()
	unique_sum = set(unique_sum)
	ans = 0 
	# print(fre÷q)

	for i in unique_sum:
		if i!=0 and a%i==0 and a//i in freq:
			if i != a//i:
				ans += (freq[i]*freq[a//i])
			else:
				ans += (freq[i]*(freq[i]))
				freq.pop(i)

	if a == 0:
		ans = (freq[0]*len(sum_pairs))+(freq[0]*(len(sum_pairs) - freq[0]))

	# print(sum_pairs)
	print(ans)
