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

public class A {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int a = Integer.parseInt(rd.readLine());
		String L = rd.readLine();
		int n = L.length();
		int[] S = new int[n];
		for(int i=0; i<n; i++){
			S[i] = (int) (L.charAt(i)-'0');
		}
		int[] sum = new int[n];
		sum[0] = S[0];
		for(int i=1; i<n; i++)
			sum[i] = sum[i-1] + S[i];
		long[] cnt = new long[100000];
		for(int i=0; i<n; i++){
			for(int j=i; j<n; j++){
				int s = sum[j] - (i>0 ? sum[i-1] : 0);
				cnt[s]++;
			}
		}
		long res = 0;
		if(a==0){
			res += cnt[0] *n*(n+1) - cnt[0]*cnt[0];
			pw.println(res);
			pw.flush();
			return;
		}
		for(int x=1; x*x<=a; x++){
			if(a%x==0){
				if(x>=cnt.length || a/x >= cnt.length)
					continue;
				res += (cnt[x] * cnt[a/x]);
				if(a!=x*x)
					res += cnt[x]*cnt[a/x];
			}
		}
		pw.println(res);
		pw.flush();
	}

	
	
	
	
}
