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
def n_substr_sum(t, x):
# number of substrs in t that sum to x,
# assuming that t_i >= 0, x > 0
    i, j = -1, 0
    cur, n = 0, 0
    while j < len(t):
        if t[j] > x:
            i, j = j, j + 1
            cur = 0
            continue
        cur += t[j]
        while cur > x and i < j:
            i += 1
            cur -= t[i]
        if cur == x:
            mi, mj = i+1, j+1
            while mj < len(t) and t[mj] == 0:
                mj += 1 
            while mi < j and t[mi] == 0:
                mi += 1
            n += (mi-i)*(mj-j)
            i, j = mi, mj
            cur -= t[i]
        else:
            j += 1
        #print i,j,cur
    return n

a = int(raw_input().strip())
s = map(int, raw_input().strip())
n = len(s)
ts = sum(s)
#print 'length = %s' % n
ans = 0
if a > 0:
    fac = [1] + [f for f in xrange(2, int(a**0.5)+1) if a%f==0]
    for f in fac:
        if f > ts or a/f > ts: continue
        nf = n_substr_sum(s, f)
        if nf == 0: continue
        #print '%s,%s' % (f, nf)
        if a/f != f:
            nf_ = n_substr_sum(s, a/f)
            #print '%s,%s' % (a/f, nf_)
            ans += 2*nf*nf_
        else:
            ans += nf*nf
else:
    i, j = -1, 0
    nz = 0
    while j <= n:
        if j == n or s[j] != 0:
            nz += (j-i)*(j-i-1)/2
            i = j
        j += 1
    nnz = (n+1)*n/2 - nz
    ans = nz*nz + nnz*nz*2
print ans

