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 A {

    public static void main(String[] args) throws IOException {
        A solver = new A();
        solver.solve();
    }

    private void solve() throws IOException {
        FastScanner sc = new FastScanner(System.in);
//        sc = new FastScanner("10\n" +
//                "12345\n");
//        sc = new FastScanner("16\n" +
//                "439873893693495623498263984765\n");
//        sc = new FastScanner("0\n" +
//                "01\n");

        int a = sc.nextInt();
        char[] s = sc.next().toCharArray();

        int n = s.length;
        int[] psum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            psum[i] = psum[i - 1] + (s[i - 1] - '0');
        }

        Map<Integer, Integer> sums = new HashMap<Integer, Integer>();

        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int sum = psum[j] - psum[i];
                int count = 0;
                if (sums.containsKey(sum)) {
                    count = sums.get(sum);
                }
                sums.put(sum, count + 1);
            }
        }

        long res = 0;
        for (int p : sums.keySet()) {
            if (p == 0) {
                if (a == 0) {
                    long pv = sums.get(p);
                    for (int qv : sums.values()) {
                        res += pv * qv;
                    }
                }
            } else if (a % p == 0) {
                int q = a / p;
                if (sums.containsKey(q)) {
                    long pv = sums.get(p);
                    long qv = sums.get(q);
                    res += pv * qv;
                }
            }
        }

        System.out.println(res);
    }

    private static class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner(InputStream in) throws IOException {
            br = new BufferedReader(new InputStreamReader(in));
        }

        public FastScanner(File file) throws IOException {
            br = new BufferedReader(new FileReader(file));
        }

        public FastScanner(String s) {
            br = new BufferedReader(new StringReader(s));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                    return "";
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

}
