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 java.io.*;
import java.util.*;
import java.lang.*;
import java.math.BigInteger;
import java.util.Map.Entry;
import java.util.logging.Level;
import java.util.logging.Logger;


public class Main
{
    static StringTokenizer st=new StringTokenizer("");
    static BufferedReader br;
    
    ///////////////////////////////////////////////////////////////////////////////////
    
   
    public static void main(String args[]) throws FileNotFoundException, IOException, Exception
    {
        //Scanner in =new Scanner(new FileReader("input.txt"));
        //PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
        //Scanner in=new Scanner(System.in);
        br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        //StringTokenizer st;//=new StringTokenizer(br.readLine());
        //////////////////////////////////////////////////////////////////////////////////////
        
        int a=ni();
        String s=ns();
        int mat[]=new int[9*s.length()+1];
        for(int i=0;i<s.length();i++)
        {
             int sum=0;
             for(int j=i;j<s.length();j++)
             {
                 sum+=((int)s.charAt(j)-'0');
                 mat[sum]++;
             }
        }
        long ans=0;
        if(a==0)
        {
            for(int i=0;i<mat.length;i++)
                ans+=(long)mat[0]*(long)mat[i]*2l;
            ans-=(long)mat[0]*mat[0];
        }
        else 
        {
            for(int i=1;i<mat.length;i++)
                if(a%i==0 && a/i <mat.length )
                    ans+=(long)mat[i]*(long)mat[a/i];
        }
        out.print(ans);
        //////////////////////////////////////////////////////////////////////////////////////
	out.close();
    }
    
    
    
    
    ///////////////////////////////////////////////////////////////////////////////
    
    private static long gcd(long a,long b)
    {
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    private static class pair implements Comparable<pair>
    {
        int ind;
        long first;
        long second;
        pair()
        {
            ind=0;
            first=0;
            second=0;
        }
        pair(int i,long f,long s)
        {
            ind =i;
            first=f;
            second=s;
        }

        public int compareTo(pair o)
        {
            if(first <  o.first)
                return 1;
            else if(first > o.first)
                return -1;
            else
                return 0;
        }
    }
    
    public static Integer ni() throws Exception
    {
        if(!st.hasMoreTokens())
            st=new StringTokenizer(br.readLine());
        return Integer.parseInt(st.nextToken());
    }
    public static BigInteger nb()throws Exception
    {
        if(!st.hasMoreElements())
            st=new StringTokenizer(br.readLine());
        return BigInteger.valueOf(Long.parseLong(st.nextToken()));
    }
    public static Long nl() throws Exception
    {
        if(!st.hasMoreTokens())
            st=new StringTokenizer(br.readLine());
        return Long.parseLong(st.nextToken());
    }
    public static Double nd()throws Exception
    {
        if(!st.hasMoreElements())
            st=new StringTokenizer(br.readLine());
        return Double.parseDouble(st.nextToken());
    }
    public static String ns()throws Exception
    {
        if(!st.hasMoreElements())
            st=new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}