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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//long zeeeeeeeeeeeeft
public class Matrix_R365C
{
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s = sc.next();
		int n = s.length();
		int[] occ = new int[9 * n + 5];
		int cum[] = new int[n];
		cum[0] = s.charAt(0) - '0';
		for (int i = 1; i < n; i++)
			cum[i] = cum[i - 1] + s.charAt(i) - '0';
		for (int i = 0; i < n; i++)
		{
			for (int j = i; j < n; j++)
			{
				int sum = cum[j];
				if (i > 0)
					sum -= cum[i - 1];
				occ[sum]++;
			}
		}
		long cnt = 0;
		if(a == 0)
			cnt+=1l * occ[0] * n * (n + 1) - 1l * occ[0] * occ[0];
		else
		{
			for (int i = 1; i < occ.length; i++)
			{
				if (a % i != 0)
					continue;
				int comp = a / i;
				if (comp >= occ.length)
					continue;
				cnt += 1l * occ[comp] * occ[i];
			}
		}
		System.out.println(cnt);
	}

	static class Scanner
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s)
		{
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException
		{
			br = new BufferedReader(new FileReader(new File(s)));
		}

		public String next() throws IOException
		{
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException
		{
			return br.readLine();
		}

		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}

		public boolean ready() throws IOException
		{
			return br.ready();
		}
	}
}
