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
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x364A
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int A = Integer.parseInt(st.nextToken());
         String input = infile.readLine();
         int N = input.length();
         int[] arr = new int[N];
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(input.charAt(i)+"");
         if(A == 0)
         {
            ArrayList<Integer> ls = new ArrayList<Integer>();
            int curr = arr[0];
            int size = 1;
            for(int i=1; i < N; i++)
            {
               if(curr == arr[i])
                  size++;
               else
               {
                  if(curr == 0)
                     ls.add(size);
                  curr = arr[i];
                  size = 1;
               }
            }
            if(curr == 0)
               ls.add(size);
            long res = 0L;
            for(int x: ls)
               res += 2*subrect(x,N);
            for(int i=0; i < ls.size(); i++)
               for(int j=0; j < ls.size(); j++)
               {
                  int x = ls.get(i);
                  int y = ls.get(j);
                  res -= subrect(x,y);
               }
            System.out.println(res);
            return;
         }
         ArrayList<Integer> div = findDiv(A);
         HashSet<Integer> set = new HashSet<Integer>();
         for(int x: div)
            set.add(x);
         HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
         int zeros = 0;
         for(int a=0; a < N; a++)
         {
            int sum = 0;
            for(int i=a; i < N; i++)
            {
               sum += arr[i];
               if(sum == 0)
                  zeros++;
               if(!cnt.containsKey(sum) && set.contains(sum))
                  cnt.put(sum, 1);
               else if(cnt.containsKey(sum))
                  cnt.put(sum, cnt.get(sum)+1);
            }
         }
         long res = 0L;
         for(int x: cnt.keySet())
         {
            long val = (long)x;
            if(A%x == 0 && cnt.containsKey(A/x))
               res += (long)cnt.get(x)*(long)cnt.get(A/x);
         }
         System.out.println(res);
      }
      public static long subrect(long x, long y)
      {
         return (x*(x+1)*y*(y+1))/4;
      }
      public static ArrayList<Integer> findDiv(int N)
      {
         //gens all divisors of N
         ArrayList<Integer> ls1 = new ArrayList<Integer>();
         ArrayList<Integer> ls2 = new ArrayList<Integer>();
         for(int i=1; i <= (int)(Math.sqrt(N)+0.00000001); i++)
            if(N%i == 0)
            {
               ls1.add(i);
               ls2.add(N/i);
            }
         Collections.reverse(ls2);
         for(int b: ls2)
            if(b != ls1.get(ls1.size()-1))
               ls1.add(b);
         return ls1;
      }
   }