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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.File;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Atharva Nagarkar
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        JoltyScanner in = new JoltyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ProblemAMatrix solver = new ProblemAMatrix();
        solver.solve(1, in, out);
        out.close();
    }

    static class ProblemAMatrix {
        public void solve(int testNumber, JoltyScanner in, PrintWriter out) {
            int a = in.nextInt();
            char[] str = in.next().toCharArray();
            int n = str.length;
            int[] s = new int[n];
            for (int i = 0; i < n; ++i) s[i] = str[i] - '0';
            int[] csum = new int[n];
            for (int i = 0; i < n; ++i) {
                csum[i] = s[i];
                if (i > 0) csum[i] += csum[i - 1];
            }
//        {
//            int[][] grid = new int[n][n];
//            for(int i = 0; i < n; ++i) {
//                for(int j = 0; j < n; ++j) {
//                    grid[i][j] = (s[i] * s[j]);
//                }
//                System.out.println(Arrays.toString(grid[i]));
//            }
//        }
            HashMap<Integer, Integer> have = new HashMap<>();
            for (int i = 0; i < n; ++i) {
                for (int j = i; j < n; ++j) {
                    int cur = csum[j] - (i > 0 ? csum[i - 1] : 0);
                    have.put(cur, have.getOrDefault(cur, 0) + 1);
                }
            }
            long ans = 0;
            if (a == 0) {
                ans += (long) have.getOrDefault(0, 0) * n * (n + 1);
                ans -= (long) have.getOrDefault(0, 0) * have.getOrDefault(0, 0);
            } else {
                for (int x : have.keySet()) {
                    if (x == 0) continue;
                    if (a % x != 0) continue;
                    int find = a / x;
                    ans += (long) have.get(x) * have.getOrDefault(find, 0);
                }
            }
            out.println(ans);
        }

    }

    static class JoltyScanner {
        public int BS = 1 << 16;
        public char NC = (char) 0;
        public byte[] buf = new byte[BS];
        public int bId = 0;
        public int size = 0;
        public char c = NC;
        public double num = 1;
        public BufferedInputStream in;

        public JoltyScanner(InputStream is) {
            in = new BufferedInputStream(is, BS);
        }

        public JoltyScanner(String s) throws FileNotFoundException {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }

        public char nextChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            num = 1;
            boolean neg = false;
            if (c == NC) c = nextChar();
            for (; (c < '0' || c > '9'); c = nextChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = nextChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                num *= 10;
            }
            return neg ? -res : res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = nextChar();
            while (c > 32) {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

    }
}

