You have a string of decimal digits s. Let's define b_{ij} = s_{i}·s_{j}. Find in matrix b the number of such rectangles that the sum b_{ij} 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 ≤ 10^9), 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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Combinatorics

Data structures

Implementation


Solutions:
def divisors(x):

	def f(y, q):
		t = -len(r)
		while not y % q:
			y //= q
			for i in range(t, 0):
				r.append(r[t] * q)
		return y
	(r, p) = ([1], 7)
	x = f(f(f(x, 2), 3), 5)
	while x >= p * p:
		for s in (4, 2, 4, 2, 4, 6, 2, 6):
			if not x % p:
				x = f(x, p)
			p += s
	if x > 1:
		f(x, x)
	return r

def main():
	(a, s) = (int(input()), input())
	if not a:
		z = sum((x * (x + 1) for x in map(len, s.translate(str.maketrans('123456789', '         ')).split()))) // 2
		x = len(s)
		print((x * (x + 1) - z) * z)
		return
	(sums, x, cnt) = ({}, 0, 1)
	for u in map(int, s):
		if u:
			sums[x] = cnt
			x += u
			cnt = 1
		else:
			cnt += 1
	if x * x < a:
		print(0)
		return
	(sums[x], u) = (cnt, a // x)
	l = [v for v in divisors(a) if v <= x]
	z = a // max(l)
	d = {x: 0 for x in l if z <= x}
	for x in d:
		for (k, v) in list(sums.items()):
			u = sums.get(k + x, 0)
			if u:
				d[x] += v * u
	print(sum((u * d[a // x] for (x, u) in list(d.items()))))

def __starting_point():
	main()
__starting_point()


import time, math as mt, bisect as bs, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

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

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * (2 * 10 ** 5 + 5)
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(2 * 10 ** 5 + 5):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return

def readTree(n, e):
	adj = [set() for i in range(n + 1)]
	for i in range(e):
		(u1, u2) = IP()
		adj[u1].add(u2)
	return adj
mod = 10 ** 9 + 7

def solve():
	a = II()
	s = input()
	li = [int(i) for i in s]
	n = len(li)
	pref = [li[0]] + [0] * (n - 1)
	for i in range(1, n):
		pref[i] = pref[i - 1] + li[i]
	pref.insert(0, 0)
	d = {}
	for i in range(1, n + 1):
		for j in range(i, n + 1):
			val = pref[j] - pref[i - 1]
			d[val] = d.get(val, 0) + 1
	ans = 0
	if a != 0:
		for ele in d:
			if ele != 0:
				if a % ele == 0 and a // ele in d:
					ans += d[ele] * d[a // ele]
	else:
		cnt = d.get(0, 0)
		ans = 2 * cnt * (n * (n + 1) // 2) - cnt ** 2
	P(ans)
	return
t = 1
for i in range(t):
	solve()


a = int(input())
s = input()
sm = {}
for i in range(len(s)):
	for j in range(i, len(s)):
		if j == i:
			t = int(s[j])
		else:
			t += int(s[j])
		if t in sm:
			sm[t] += 1
		else:
			sm[t] = 1
if a == 0:
	if 0 in sm:
		sum_pairs = len(s) * (len(s) + 1) // 2
		print(sm[0] * sum_pairs + sm[0] * (sum_pairs - sm[0]))
	else:
		print(0)
else:
	c = 0
	for f in sm:
		if f != 0 and a % f == 0 and (a // f in sm):
			c += sm[f] * sm[a // f]
	print(c)


a = int(input())
b = [int(i) for i in input()]
n = len(b)
c = [0] * (sum(b) + 1)
d = [0]
e = 0
for i in range(n):
	e += b[i]
	d.append(e)
for i in range(n):
	for j in range(i, n):
		c[d[j + 1] - d[i]] += 1
if a == 0:
	print(2 * c[0] * sum(c) - c[0] ** 2)
else:
	f = 0
	c1 = len(c)
	for i in range(1, int(a ** 0.5) + 1):
		if a % i == 0 and i < c1 and (a // i < c1):
			f += c[i] * c[a // i]
			if i != a // i:
				f += c[a // i] * c[i]
	print(f)


def f(t, k):
	(i, j) = (0, 1)
	(s, d) = (0, t[0])
	n = len(t)
	while j <= n:
		if d > k:
			d -= t[i]
			i += 1
		elif d == k:
			if t[i] and (j == n or t[j]):
				s += 1
			else:
				(a, b) = (i - 1, j - 1)
				while j < n and t[j] == 0:
					j += 1
				while t[i] == 0:
					i += 1
				s += (i - a) * (j - b)
			if j < n:
				d += t[j]
			d -= t[i]
			i += 1
			j += 1
		else:
			if j < n:
				d += t[j]
			j += 1
	return s
(s, n) = (0, int(input()))
t = list(map(int, input()))
if n:
	k = sum(t)
	if k == 0:
		print(0)
	else:
		p = [(i, n // i) for i in range(max(1, n // k), int(n ** 0.5) + 1) if n % i == 0]
		for (a, b) in p:
			if a != b:
				s += 2 * f(t, a) * f(t, b)
			else:
				k = f(t, a)
				s += k * k
		print(s)
else:
	n = len(t)
	m = n * (n + 1)
	s = j = 0
	while j < n:
		if t[j] == 0:
			i = j
			j += 1
			while j < n and t[j] == 0:
				j += 1
			k = (j - i) * (j - i + 1) // 2
			s += k
		j += 1
	print((m - s) * s)


import os
import sys
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')
from collections import Counter
import heapq
import math
from collections import Counter
from bisect import bisect_right
n = int(input())
s = input()
l = len(s)
d = [0] * 36001
for i in range(l):
	ss = 0
	for j in range(i, l):
		ss += int(s[j])
		d[ss] += 1
if n == 0:
	ans = 0
	for i in range(1, 36001):
		ans += d[0] * d[i] * 2
	ans += d[0] * d[0]
	print(ans)
else:
	ans = 0
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if i == n // i:
				ans += d[i] * d[i]
			elif n // i <= 36000:
				ans += 2 * d[i] * d[n // i]
	print(ans)


import sys
import itertools as it
import bisect as bi
import math as mt
import collections as cc
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(a,) = I()
s = list(input().strip())
n = len(s)
s = [int(s[i]) for i in range(len(s))]
f = cc.defaultdict(int)
for i in range(n):
	tem = 0
	for j in range(i, n):
		tem += s[j]
		f[tem] += 1
temp = list(f.keys())
if a == 0:
	tot = n * (n + 1) // 2
	tot = tot ** 2
	if f[0]:
		del f[0]
	tem = sum(f.values())
	for i in f:
		tot -= tem * f[i]
	print(tot)
else:
	ans = 0
	for i in temp:
		if i != 0:
			if a % i == 0:
				j = a // i
				if f[i] > 0 and f[j] > 0:
					ans += f[i] * f[j]
	print(ans)


from collections import Counter
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
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(ans)


from collections import Counter
a = int(input())
string = input()
arr = [0]
count1 = 0
count2 = 0
for i in range(len(string)):
	arr += [int(string[i])]
for i in range(1, len(arr)):
	arr[i] += arr[i - 1]
temparr = []
for i in range(len(arr)):
	for j in range(i + 1, len(arr)):
		temparr += [arr[j] - arr[i]]
sumset = Counter(temparr)
possums = 0
for i in sumset:
	possums += sumset[i]
for i in sumset:
	if i != 0 and a % i == 0 and (i ** 2 != a):
		count1 += sumset[i] * sumset[a // i]
	elif i == 0 and a == 0:
		count1 += sumset[i] * possums
	elif i != 0 and a % i == 0 and (i ** 2 == a):
		count2 += sumset[i] * sumset[a // i]
print(count1 + count2)


import sys
from math import log2, floor, ceil, sqrt
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
a = int(ri())
st = ri()
arr = [int(i) for i in st]
dic = {}
cnt = 0
nz = 0
for i in range(len(st)):
	summ = 0
	for j in range(i, len(st)):
		summ += arr[j]
		if summ != 0:
			nz += 1
		if summ in dic:
			dic[summ] += 1
		else:
			dic[summ] = 1
if a != 0:
	for i in dic:
		if i != 0:
			val = a / i
			if val in dic:
				cnt = cnt + dic[val] * dic[i]
	print(cnt)
else:
	n = len(st)
	print(n ** 2 * (n + 1) ** 2 // 4 - nz * nz)


sm = [0] * 40000
n = int(input())
s = input()
l = len(s)
for i in range(l):
	ss = 0
	for j in range(i, l):
		ss += int(s[j])
		sm[ss] += 1
if n == 0:
	ans = 0
	for i in range(1, 40000):
		ans += sm[0] * sm[i] * 2
	ans += sm[0] * sm[0]
	print(ans)
else:
	ans = 0
	u = int(n ** 0.5)
	for i in range(1, u + 1):
		if n % i == 0:
			if n // i < 40000:
				ans += sm[i] * sm[n // i]
	ans *= 2
	if u ** 2 == n:
		ans -= sm[u] ** 2
	print(ans)


from collections import defaultdict
a = int(input())
s = list(input())
n = len(s)
for i in range(n):
	s[i] = int(s[i])
cs = [0] + s
for i in range(1, n + 1):
	cs[i] += cs[i - 1]
cnt = defaultdict(int)
key = set()
for l in range(1, n + 1):
	for r in range(l, n + 1):
		cnt[cs[r] - cs[l - 1]] += 1
		key.add(cs[r] - cs[l - 1])
if a == 0:
	if 0 in cnt:
		y = n * (n + 1) // 2
		print(y * cnt[0] + cnt[0] * (y - cnt[0]))
	else:
		print(0)
	exit()
ans = 0
for x in key:
	if x > 0 and a % x == 0 and (a // x in key):
		ans += cnt[x] * cnt[a // x]
print(ans)


from math import *
import sys
input = sys.stdin.readline
global flag

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = 1

def pos(su, le):
	if su >= 0 and su <= 9 * le:
		return 1
	return 0
while t:
	t -= 1
	a = inp()
	s = st()
	di = {}
	for i in range(len(s)):
		su = 0
		for j in range(i, len(s)):
			su += int(s[j])
			try:
				di[su] += 1
			except:
				di[su] = 1
	co = 0
	for i in di.keys():
		if a == 0 and i == 0:
			co += di[0] * (len(s) * (len(s) + 1))
			co -= di[0] * di[0]
		if i and a % i == 0 and (a // i in di) and a:
			co += di[i] * di[a // i]
	print(co)


import sys
from collections import defaultdict as dd
from collections import deque

def eprint(*args):
	print(*args, file=sys.stderr)
pl = 1
from math import *
import copy
if pl:
	input = sys.stdin.readline

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

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

def mi():
	return map(int, input().split())
d = []
from bisect import *
from itertools import permutations
from bisect import *
f = [0 for i in range(100)]
for i in range(1, 100):
	if i == 1:
		f[i] = 1
	else:
		f[i] = 2 * f[i - 1] + 1

def rec(n, k):
	s = []
	while n != 0:
		(n, r) = (n // k, n % k)
		if r < 0:
			r -= k
			n += 1
		s.append(r)
	return s
n = fi()
s = si()
a = []
for i in range(len(s)):
	a.append(int(s[i]))
d = {}
nn = len(s)
for i in range(nn):
	c = 0
	for j in range(i, nn):
		c += a[j]
		if c not in d:
			d[c] = 1
		else:
			d[c] += 1
ans = 0
if n == 0 and 0 in d:
	for j in d:
		if j == 0:
			ans += d[0] * d[0]
		else:
			ans += d[j] * d[0] * 2
for j in range(1, int(sqrt(n)) + 1):
	if n % j == 0:
		if n // j == j:
			if j in d:
				ans += d[j] * d[j]
		elif n // j in d and j in d:
			ans += d[j] * d[n // j] * 2
print(ans)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase

def main():
	a = int(input())
	digit = [int(x) for x in input()]
	n = len(digit)
	accumulated = [0] * n
	accumulated[0] = digit[0]
	for i in range(1, n):
		accumulated[i] = accumulated[i - 1] + digit[i]
	intervalSums = {}
	for i in range(n):
		for j in range(i, n):
			value = accumulated[j] - (accumulated[i - 1] if i > 0 else 0)
			if value in intervalSums:
				intervalSums[value] += 1
			else:
				intervalSums[value] = 1
	numOfRectangles = 0
	possibleSegments = (n ** 2 + n) // 2
	for intervalSum in intervalSums:
		if intervalSum == 0:
			if a == 0:
				numOfRectangles += possibleSegments * intervalSums[0]
			continue
		if a % intervalSum == 0:
			complement = a // intervalSum
			numOfRectangles += intervalSums[intervalSum] * (intervalSums[complement] if complement in intervalSums else 0)
	print(numOfRectangles)
BUFFSIZE = 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, BUFFSIZE))
			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, BUFFSIZE))
			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')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


a = int(input())
s = input()
di = {}
for i in range(len(s)):
	total = 0
	for j in range(i, len(s)):
		total += int(s[j])
		di[total] = 1 if total not in di else di[total] + 1
ans = 0
if a == 0:
	ans = 0
	if 0 in di:
		ans += di[0] * di[0]
		for each in di:
			if not each:
				continue
			ans += di[each] * di[0] * 2
	print(ans)
	quit()
for p in di:
	if p and a % p == 0 and (a // p in di):
		ans += di[a // p] * di[p]
print(ans)


import sys
from math import gcd, sqrt, ceil, log2
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
sys.setrecursionlimit(2 * 10 ** 5 + 10)
import heapq
from itertools import permutations
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
aa = 'abcdefghijklmnopqrstuvwxyz'

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

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = []
	while n % 2 == 0:
		sa.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.append(i)
			n = n // i
	if n > 2:
		sa.append(n)
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def check_prim(n):
	if n < 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def getZarr(string, z):
	n = len(string)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and string[r - l] == string[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1

def search(text, pattern):
	concat = pattern + '$' + text
	l = len(concat)
	z = [0] * l
	getZarr(concat, z)
	ha = []
	for i in range(l):
		if z[i] == len(pattern):
			ha.append(i - len(pattern) - 1)
	return ha

def mergeIntervals(arr):
	arr.sort(key=lambda x: x[0])
	m = []
	s = -10000
	max = -100000
	for i in range(len(arr)):
		a = arr[i]
		if a[0] > max:
			if i != 0:
				m.append([s, max])
			max = a[1]
			s = a[0]
		elif a[1] >= max:
			max = a[1]
	if max != -100000 and [s, max] not in m:
		m.append([s, max])
	return m

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def sol(n):
	seti = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			seti.add(n // i)
			seti.add(i)
	return seti

def lcm(a, b):
	return a * b // gcd(a, b)

def moore_voting(l):
	count1 = 0
	count2 = 0
	first = 10 ** 18
	second = 10 ** 18
	n = len(l)
	for i in range(n):
		if l[i] == first:
			count1 += 1
		elif l[i] == second:
			count2 += 1
		elif count1 == 0:
			count1 += 1
			first = l[i]
		elif count2 == 0:
			count2 += 1
			second = l[i]
		else:
			count1 -= 1
			count2 -= 1
	for i in range(n):
		if l[i] == first:
			count1 += 1
		elif l[i] == second:
			count2 += 1
	if count1 > n // 3:
		return first
	if count2 > n // 3:
		return second
	return -1

def dijkstra(n, tot, hash):
	hea = [[0, n]]
	dis = [10 ** 18] * (tot + 1)
	dis[n] = 0
	boo = defaultdict(bool)
	while hea:
		(a, b) = heapq.heappop(hea)
		if boo[b]:
			continue
		boo[b] = True
		for (i, w) in hash[b]:
			if dis[b] + w < dis[i]:
				dis[i] = dis[b] + w
			heapq.heappush(hea, [dis[i], i])
	return dis

def find_parent(u, parent):
	if u != parent[u]:
		parent[u] = find_parent(parent[u], parent)
	return parent[u]

def dis_union(n):
	par = [i for i in range(n + 1)]
	rank = [1] * (n + 1)
	k = int(input())
	for i in range(k):
		(a, b) = map(int, input().split())
		(z1, z2) = (find_parent(a, par), find_parent(b, par))
		if z1 != z2:
			par[z1] = z2
			rank[z2] += rank[z1]
a = int(input())
l = list(input())
n = int(len(l))
hash = defaultdict(int)
for i in range(n):
	tot = 0
	for j in range(i, n):
		tot += int(l[j])
		hash[tot] += 1
ans = 0
if a == 0:
	ans += hash[0] * hash[0]
	for i in hash:
		if not i:
			continue
		ans += hash[0] * hash[i] * 2
	print(ans)
	exit()
for i in hash:
	if i and a % i == 0 and (a // i in hash):
		ans += hash[a // i] * hash[i]
print(ans)


a = int(input())
s = input()
d = {}
for i in range(len(s)):
	for j in range(i, len(s)):
		if j == i:
			t = int(s[j])
		else:
			t += int(s[j])
		d[t] = d.get(t, 0) + 1
if a == 0:
	if 0 in d:
		cnt_pairs = len(s) * (len(s) + 1) // 2
		print(d[0] * cnt_pairs + d[0] * (cnt_pairs - d[0]))
	else:
		print(0)
else:
	c = 0
	for f in d:
		if f != 0 and a % f == 0 and (a // f in d):
			c += d[f] * d[a // f]
	print(c)


import sys, collections as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(a,) = I()
s = list(map(int, [i for i in input().strip()]))
d = cc.Counter([])
n = len(s)
for i in range(1, n + 1):
	su = sum(s[:i])
	for j in range(i, n):
		d[su] += 1
		su = su - s[j - i] + s[j]
	d[su] += 1
an = 0
if a == 0:
	an = (n * (n + 1) // 2) ** 2
	del d[0]
	xx = sum(d.values())
	for i in d:
		an -= d[i] * xx
else:
	for i in d.keys():
		if i != 0 and a % i == 0:
			an = an + d[i] * d[a // i]
print(an)