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.*;
public class A 
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		
		char[] str = in.next().trim().toCharArray();
		
		int[] s = new int[str.length];
		for(int x = 0; x < str.length; x++)
		{
			s[x] = str[x] - '0';
		}
		
		int[] prefix = new int[s.length + 1];
		prefix[0] = 0;
		for(int y = 0; y < s.length; y++)
		{
			prefix[y + 1] = prefix[y] + s[y];
		}
		
		int[] freq = new int[100001];
		int total = 0;
		for(int z = 1; z < prefix.length; z++)
		{
			for(int b = 1; b <= z; b++)
			{
				freq[prefix[z] - prefix[b - 1]]++;
				total++;
			}
		}
		
		long result = 0;
		for(int c = 1; c < prefix.length; c++)
		{
			for(int d = 1; d <= c; d++)
			{
				int current = prefix[c] - prefix[d - 1];
				
				if(a != 0 && current != 0 && a % current == 0)
				{
					if(a / current < freq.length)
					{
						result += freq[a / current];
					}
				}
				else if(a == 0)
				{
					if(current == 0)
					{
						result += total;
					}
					else
					{
						result += freq[0];
					}
				}
			}
		}
		
		System.out.println(result);
	}
}
