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.*;


public class test {
    int INF = (int)1e9;
    long MOD = 1000000007;
    
    int go(int[] a, int s) {
        int n = a.length;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        int p = 0;
        int rs = 0;
        for(int i=0; i<n; i++) {
            p += a[i];
            if(mp.containsKey(p-s)) {
                rs += mp.get(p-s);
            }
            mp.put(p, mp.getOrDefault(p, 0)+1);
        }
        return rs;
    }

    void solve(InputReader in, PrintWriter out) throws IOException {
        int a = in.nextInt();
        String ss = in.next();
        int n = ss.length();
        int[] s = new int[n];
        for(int i=0; i<n; i++) {
            s[i] = (int)(ss.charAt(i)-'0');
        }

        int[] p = new int[n];
        p[0] = s[0];
        for(int i=1; i<n; i++) {
            p[i] = s[i] + p[i-1];
        }

        HashMap<Integer, Integer> mp = new HashMap<>();
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {
                int x = p[j] - (i>0?p[i-1]:0);
                mp.put(x, mp.getOrDefault(x, 0)+1);
            }
        }

        int t = (n*(n+1))/2;
        
        long rs = 0;

        for(int c1=0; c1<n; c1++) {
            for(int c2=c1; c2<n; c2++) {
                int cols = p[c2] - (c1>0?p[c1-1]:0);
                if(cols!=0 && a % cols == 0) {
                    int x = //go(s, a/cols);
                        mp.getOrDefault(a/cols, 0);
                    rs += x;
                    // show(c1, c2, cols, "cal", x);
                } else if(cols==0 && a==0) {
                    // show(c1, c2, cols, "whl", t);
                    rs += t;
                }
            }
        }
        out.println(rs);
    }
    
    
    public static void main(String[] args) throws IOException {
        if(args.length>0 && args[0].equalsIgnoreCase("d")) {
            DEBUG_FLAG = true;
        }
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;//in.nextInt();
        long start = System.nanoTime();
        while(t-- >0) {
            new test().solve(in, out);
        }
        long end = System.nanoTime();
        debug("\nTime: " + (end-start)/1e6 + " \n\n");
        out.close();
    }
    
    static boolean DEBUG_FLAG = false;
    static void debug(String s) {
        if(DEBUG_FLAG) System.out.print(s);
    }
    
    public static void show(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    
    static class InputReader {
        static BufferedReader br;
        static StringTokenizer st;
    
        public InputReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                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());
        }
    }
}