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.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        boolean debug = false;

        InputStream input = System.in;
        if (debug) {
            input = new FileInputStream("input.in");
        }

        Scanner in = new Scanner(input);
        int a = in.nextInt();
        String chars = in.next();
        ArrayList<Integer> vals = new ArrayList<Integer>();
        for (int i = 0; i < chars.length(); i++) {
            vals.add(Integer.parseInt(chars.substring(i, i + 1)));
        }

        long allWays = 0;
        Map<Integer, Long> waysMap = new HashMap<Integer, Long>();
        for (int i = 0; i < chars.length(); i++) {
            int total = 0;
            for (int j = i; j < chars.length(); j++) {
                total += vals.get(j);
                if (!waysMap.containsKey(total)) {
                    waysMap.put(total, (long) 0);
                }
                waysMap.put(total, waysMap.get(total) + 1);
                allWays += 1;
            }
        }

        long total = 0;
        if (a == 0) {
            //System.out.println("a == 0");
            if (waysMap.containsKey(0)) {
                //System.out.println("Got zero");
                long zWays = waysMap.get(0);
                total = (zWays * allWays * 2) - (zWays * zWays);
            }
        } else {
            for (Map.Entry<Integer, Long> entry: waysMap.entrySet()) {
                int x = entry.getKey();
                long xWays = entry.getValue();
                if (x == 0) {
                    continue;
                } else if (a % x == 0) {
                    //System.out.println(xWays + " ways to make " + x);
                    int y = a / x;
                    if (waysMap.containsKey(y)) {
                        long yWays = waysMap.get(y);
                        total += xWays * yWays;
                    }
                }
            }
        }

        System.out.println(total);
    }
}
