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{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	if (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	   return Integer.parseInt(next());
    }
    
    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);

	int N = nextInt();
	char []a = next().toCharArray();
	int n = a.length;
	int s[] = new int[n];
	s[0] = a[0] - '0';
	for(int i=1;i<n;i++) s[i] = s[i-1] + a[i] - '0';
	
	Map<Integer, Long> map = new HashMap<Integer, Long>();
	for(int i=0;i<n;i++){
	    for(int j=i;j<n;j++){
		int x = s[j] - (i==0 ? 0 : s[i-1]);
		long c = 0;
		if (map.containsKey(x)) c = map.get(x);
		map.put(x, c + 1);
	    }
	}
	
	Set<Integer> factors = new HashSet<Integer>();
	for(int i=1;i<=Math.sqrt(N);i++){
	    if (N % i == 0){
		factors.add(i);
		factors.add(N/i);
	    }
	}
	
	long ret = 0;
	for(int f : factors){
	    if (map.containsKey(f) && map.containsKey(N/f)){
		ret+=map.get(f) * map.get(N/f);
	    }
	}
	if (N == 0){
	    if (map.containsKey(0)){
		ret = map.get(0) * (n * (n+1) - map.get(0));
	    }
	}
	out.println(ret);
	out.close();
    }

    public static void main(String args[]) throws Exception{
	   new Main().run();
    }
}