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

public class A364 {

	public static BufferedReader read = null;
	public static PrintWriter out = null;
	public static StringTokenizer token = null;
	
	
	public static void solve()
	{
		int a = nint();
		String in = next();
		int n = in.length();
		int[] s = new int[n];
		for(int i=0; i<n; i++) s[i] = in.charAt(i)-'0';
		int[][] sum = new int[n][n]; //sum[l][r] = sum of all s_i l<=i<=r
		int occ[] = new int[9*n+1];
		for(int l=0; l<n; l++)
		{
			for(int r=l; r<n; r++)
			{
				if(r == l) sum[l][r] = s[r];
				else sum[l][r] = sum[l][r-1] + s[r];
				occ[sum[l][r]]++;
			}
		}
		long ct = 0;
		for(int l =0; l<n; l++)
		{
			for(int r = l; r<n; r++)
			{
				if(sum[l][r] == 0)
				{
					if(a == 0)
					{
						ct+=n*(n+1)/2;
					}
				}
				else if (a == 0)
				{
					ct+=occ[0];
				}
				else if(a%sum[l][r] == 0)
				{
					if(a/sum[l][r] <= 9*n) ct+=occ[a/sum[l][r]];
				}
			}
		}
		out.println(ct);
	}
	
	public static void main(String[] args)
	{
		read = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.flush();
		out.close();
		
	}
	
	// i/o functions
	public static String next() // returns the next string
	{
		while(token == null || !token.hasMoreTokens())
		{
			try {
				token = new StringTokenizer(read.readLine());
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		return token.nextToken();
	}
	
	public static int nint()
	{
		return Integer.parseInt(next());
	}
	public static long nlong()
	{
		return Long.parseLong(next());
	}
	public static double ndouble()
	{
		return Double.parseDouble(next());
	}
	public static int[] narr(int n)
	{
		int[] a = new int[n];
		for(int i=0; i<n; i++) a[i] = nint();
		return a;
	}
	
	public static long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i=0; i<n; i++) a[i] = nlong();
		return a;
	}
	
	
}
