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
import math
def main(arr,a):


  f=[] 

  for i in range(1,int(math.sqrt(a))+1):
    
    f1=i 
    f2=a/i 
    if f2==int(f2):
      f.append(f1)
      if f2!=f1:
        f.append(int(f2))
  f.sort()
  
  
  prefix=[0] 
  
  for i in range(len(arr)):
    prefix.append(prefix[-1]+arr[i])
  
  diff={} 
 
  for i in range(len(prefix)):
    for j in range(0,i):
      val= prefix[i]-prefix[j]
      if val not in diff:
        diff[val]=0 
      diff[val]+=1 
  if a==0:
    for e in diff:
      f.append(e) 
      f.append(0)
    f.sort()
  ans=0
  i=0 
  j=len(f)-1 
  
  while i<=j:
    f1=f[i] 
    f2=f[j]
    
    if f1 in diff and f2 in diff:
      if f1==f2:
        ans+=diff[f1]*diff[f2]
      else:

        ans+=2*(diff[f1]*diff[f2])
    i+=1 
    j-=1
  return ans 

    
  

a=int(input())
arr=[int(c) for c in input()]
print(main(arr,a))  