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.math.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                                            //(new FileReader("input.in"));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        //PrintWriter pw = new PrintWriter("output.out", "UTF-8");
        
        int a = parseInt(in.readLine());
        String s = in.readLine();
        int n = s.length();
        
        int [] sum = new int[n];
        sum[0] = s.charAt(0)-'0';
        for(int i=1; i<n; i++)
            sum[i] = sum[i-1]+(s.charAt(i)-'0');
        
        int [] freq = new int[n*9+1];
        
        for(int i=0; i<n; i++)
            for(int j=i; j<n; j++)
                freq[sum[j]-(i==0 ? 0 : sum[i-1])]++;
        
        long ans = 0;
       
        if(a == 0) {
            Set<Integer> ss = new HashSet<Integer>();
            int [] f = new int[n+1];
            long x = 0;
            for(int i=0; i<n; i++)
                for(int j=i; j<n; j++)
                    if(sum[j]-(i==0?0:sum[i-1]) == 0) {
                        f[j-i+1]++;
                        x++;
                        ss.add(j-i+1);
                    }
            
            long i=2,r = 1;
            for(;i<=n; i++)
                r += i;
            System.out.println(r*r-(r-x)*(r-x));
            return;
        }
        
        for(int i=1; i<freq.length; i++) {
            if(freq[i]>0 && a%i==0 && a/i<=n*9) {
               // System.out.println(i+" "+(a/i)+" "+freq[a/i]);
                //if(i > a/i) break;
                ans += (long)freq[i]*(long)freq[a/i];
            }
        }
        
        System.out.println(ans);
    } 
}
