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 math import *
#from bisect import *
#from collections import *
#from random import *
#from decimal import *"""
#from heapq import *
#from random import *
import sys
input=sys.stdin.readline
#sys.setrecursionlimit(3*(10**5))
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)
            
            
