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.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong(); 
    	int L = 4000 * 11;
    	String dec = sc.next();
		char []input = dec.toCharArray();
		long[] sum = new long[input.length + 1];
    	long total = 0;
    	for(int p = 0; p < input.length; p++){
    		total += (long)(input[p] - '0'); 
    		sum[p + 1] = total;	
    	}

    	long[] counts = new long[L];
    	for(int l = 1; l <= input.length; l++){
        	for(int r = l; r <= input.length; r++){
        	    long temp = sum[r] - sum[l - 1];
        	    ++counts[(int)temp];
        	}
    	}

    	long output = 0;
    	if(a > 0){
    		for(int p = 1; p * p <= a ; p++){
        		if(p >= counts.length || (a / p) >= counts.length){
        			continue;
        		}
        		if(a % p == 0){
        			output += ((p * p == a) ? 1 : 2) * counts[p] * counts[(int)a / p];
        		}
    		}
    	}
    	else{
    		output = counts[0] * (input.length * (input.length + 1) - counts[0]);
		}
		System.out.println(output);
	}
}