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

public class Main {

	static class FastScanner {
		BufferedReader s;
		StringTokenizer st;

		public FastScanner(InputStream InputStream) {
			st = new StringTokenizer("");
			s = new BufferedReader(new InputStreamReader(InputStream));
		}

		public FastScanner(File f) throws FileNotFoundException {
			st = new StringTokenizer("");
			s = new BufferedReader(new FileReader(f));
		}

		public int nextInt() throws IOException {
			if (st.hasMoreTokens())
				return Integer.parseInt(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextInt();
			}
		}

		public BigInteger big() throws IOException {
			if (st.hasMoreTokens())
				return new BigInteger(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return big();
			}
		}

		public double nextDouble() throws IOException {
			if (st.hasMoreTokens())
				return Double.parseDouble(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextDouble();
			}
		}

		public long nextLong() throws IOException {
			if (st.hasMoreTokens())
				return Long.parseLong(st.nextToken());
			else {
				st = new StringTokenizer(s.readLine());
				return nextLong();
			}
		}

		public String next() throws IOException {
			if (st.hasMoreTokens())
				return st.nextToken();
			else {
				st = new StringTokenizer(s.readLine());
				return next();
			}

		}

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

		public void close() throws IOException {
			s.close();
		}

	}

	public static void main(String[] args) throws java.lang.Exception {
		FastScanner in = new FastScanner(System.in);
		int a = in.nextInt();
		String str = in.next();
		int n = str.length();
		int sum[] = new int[n + 1];
		HashMap<Integer, Integer> fmap = new HashMap();
		for(int x = 1; x <= n; x++) 
			sum[x] += sum[x- 1] + str.charAt(x - 1) - '0';
		for(int x = 1; x <= n; x++) {
			for(int y = x; y <= n; y++) {
				int val = sum[y] - sum[x - 1];
				fmap.put(val, fmap.getOrDefault(val, 0) + 1);
			}
		}
		long ans = 0;
		for(int x = 1; x <= n; x++) {
			for(int y = x; y <= n; y++) {
				int val = sum[y] - sum[x - 1];
				if(val != 0 && a % val == 0) {
					val = a / val;
					if(fmap.containsKey(val))
						ans += fmap.get(val);
				}
				else if(val == 0 && a == 0) {
					ans += ((n + 1)* n )/2;
				}
			}
		}		
		System.out.println(ans);
	}
}
