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

Difficulty: competition

Starter code:

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

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

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


# Made By Mostafa_Khaled

__starting_point()

import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

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



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]
#print(arr)
temparr=[]
#sumset.add(arr[0])
for i in range(len(arr)):
  for j in range(i+1,len(arr)):
    temparr+=[(arr[j]-arr[i])]
sumset=Counter(temparr)
#print(sumset)
possums=0
for i in (sumset):
  possums+=sumset[i]
for i in (sumset):
  #print(str(i)+"###")
  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:
    #print(str(i)+"***")
    count2+=sumset[i]*sumset[a//i]

print(count1+count2)

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


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.14159265358979323846264338327950
def II(): # to take integer input
    return int(stdin.readline())
def IP(): # to take tuple as input
    return list(map(int,stdin.readline().split()))
def L(): # to take list as input
    return list(map(int,stdin.readline().split()))
def P(x): # to print integer,list,string etc..
    return stdout.write(str(x)+"\n")
def PI(x,y): # to print tuple separatedly
    return stdout.write(str(x)+" "+str(y)+"\n")
def lcm(a,b): # to calculate lcm
    return (a*b)//gcd(a,b)
def gcd(a,b): # to calculate gcd
    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): # a schema of bfs
    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): # to read tree
    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()

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)

from collections import Counter
def __starting_point():
	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 = list(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)

__starting_point()

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)