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.util.*;
import java.io.*;
import static java.lang.Math.*;
 
public class Main
{
    /*
     * This FastReader code is taken from GeeksForGeeks.com
     * https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
     *
     * The article was written by Rishabh Mahrsee
     */
    public static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
 
    public static FastReader in = new FastReader();
    public static PrintWriter out = new PrintWriter(System.out);
    public static final int MOD = (int)1e9 + 7;
 
    public static void main(String[] args)
    {
        // Use long to prevent overflow
        int[] occurances = new int[36001];
        long totalOccurances = 0;
        int a = in.nextInt();
        char[] str = in.nextLine().toCharArray();
        int n = str.length;
        
        int[] pref = new int[n];
        pref[0] = str[0]-'0';
        
        for (int i = 1; i < n; i++)
        {
            pref[i] = pref[i - 1] + (str[i]-'0');
        }
        
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                occurances[pref[i] - (j - 1 > -1 ? pref[j - 1] : 0)]++;
                totalOccurances++;
            }
        }
        
        long answer = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                int curSum = pref[i] - (j - 1 > -1 ? pref[j - 1] : 0);
                
                if (curSum == 0 && a == 0)
                {
                    answer += totalOccurances;
                }
                
                else if (curSum != 0 && a % curSum == 0)
                {
                    answer += a / curSum < occurances.length ? occurances[a / curSum] : 0;
                }
            }
        }
        
        out.println(answer);
        
        out.close();
    }
 
 
 
}













