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.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.ArrayBlockingQueue;


public class ProblemA {
	

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		long n = in.nextLong();
		char[] c = in.next().toCharArray();
		int[] imos = new int[c.length+1];
		for (int i = 0 ; i < c.length ; i++) {
			imos[i+1] = imos[i] + c[i] - '0';
		}
		long[] freq = new long[40000];
		for (int i = 0 ; i < c.length ; i++) {
			for (int j = i+1 ; j <= c.length ; j++) {
				freq[imos[j]-imos[i]]++;
			}
		}
		
		long ans = 0;
		for (int i = 1 ; i < freq.length ; i++) {
			if (n % i == 0) {
				int a = i;
				int b = (int)n/i;
				if (a < freq.length && b < freq.length) {
					ans += freq[a] * freq[b];
				}
			}
		}
		if (n == 0) {
			ans *= 2;
			ans += freq[0] * freq[0];
		}
		
		out.println(ans);
		out.flush();
	}
	
	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}
