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

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().run(in, out);
        out.close();
    }

    void run(FastScanner in, PrintWriter out) {

        long a = in.nextInt();
        char[] ca = in.next().toCharArray();
        int n = ca.length;

        Map<Long, Long> rangeSumCount = new HashMap<>();

        long cnt = 0;
        for (int l = 0; l < n; l++) {
            long sum = 0;
            for (int r = l; r < n; r++) {
                sum += ca[r]-'0';
                long prev = rangeSumCount.getOrDefault(sum, 0L);
                rangeSumCount.put(sum, prev + 1);
            }
        }

        for (long l : rangeSumCount.keySet()) {
            if (a == 0) {
                cnt += rangeSumCount.getOrDefault(0L, 0L) * rangeSumCount.get(l);
            }
            if (l != 0 && (a%l == 0) && rangeSumCount.containsKey(a/l)) {
                cnt += rangeSumCount.get(l) * rangeSumCount.get(a/l);
            }
        }


        out.println(cnt);
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }

        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());
        }
    }
}
