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.*;
public class a {
public static void main(String[] args)
{
    Scanner input = new Scanner(System.in);
    int a = input.nextInt();
    TreeSet<Integer> factors = new TreeSet<Integer>();
    for(int i = 1; i<=Math.sqrt(a); i++)
        if(a%i == 0)
        {
            factors.add(i);
            factors.add(a/i);
        }
    int[] count = new int[100000];
    String s = input.next();
    int n = s.length();
    int[] data = new int[n];
    for(int i = 0; i<n; i++) data[i] = s.charAt(i) - '0';
    int[] sums = new int[n];
    sums[0] = data[0];
    for(int i = 1; i<n; i++) sums[i] = sums[i-1] + data[i];
    for(int i = 0; i<n; i++)
        for(int j = i; j<n; j++)
        {
            int x = sums[j] - (i == 0 ? 0 : sums[i-1]);
            //System.out.println(x);
            count[x]++;
        }
    long res = 0;
    for(int x: factors)
    {
        if(x < 100000 && a/x < 100000)
        res += (long)count[x]*count[a/x];
    }
    if(a == 0) res += (long)count[0]*(n*(n+1)) - (long)count[0]*count[0];
    System.out.println(res);
}
}
