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.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class TaskC
{
    Scanner in;
    PrintWriter out;

    int n, a;
    long ans = 0;
    String numbers;
    HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();

    public static void main(String[] args)
    {
        TaskC mainTest = new TaskC();

        mainTest.readData();
        mainTest.solve();
        mainTest.outputData();
    }

    public TaskC()
    {
        in = new Scanner(System.in);
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }

    public void readData()
    {
        a = in.nextInt();
        in.nextLine();

        numbers = in.nextLine();
        n = numbers.length();
    }

    public void solve()
    {
        int[] nums = new int[n];

        for (int i = 0; i < n; i++ )
        {
            nums[i] = numbers.charAt(i) - '0';
        }

        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += nums[j];
                int cur = count.containsKey(sum) ? count.get(sum) : 0;
                count.put(sum, cur + 1);
            }
        }

        for (int i = 1; i <= Math.sqrt(a); i++)
        {
            if (a % i == 0) {
                int first = i;
                int second = a / first;

                long c1 = count.containsKey(first) ? count.get(first) : 0;
                long c2 = count.containsKey(second) ? count.get(second) : 0;
                if (first == second)
                {
                    ans += c1 * c2;
                } else {
                    ans += c1 * c2 * 2;
                }
            }
        }

        if (a == 0) {
            long c0 = count.containsKey(0) ? count.get(0) : 0;
            ans = c0 * n * (n + 1) - c0 * c0;
        }
    }

    public void outputData()
    {
        out.println(ans);
        out.flush();
    }

}
