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
//package CF;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class B {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int a = sc.nextInt();
		char[] c = sc.next().toCharArray();
		int n = c.length;
		int[] cum = new int[n];
		cum[0] = c[0] - '0';
		for (int i = 1; i < c.length; i++) {
			cum[i] += cum[i - 1] + c[i] - '0';
		}
		HashMap<Integer, Long> mp = new HashMap<>();
		for (int i = 0; i < cum.length; i++) {
			for (int j = i; j < cum.length; j++) {
				int res = cum[j] - (i > 0 ? cum[i - 1] : 0);
				Long tmp = mp.get(res);
				if (tmp == null)
					tmp = 0L;
				mp.put(res, tmp + 1);
			}
		}
		long ans = 0;
		for (int i = 0; i < cum.length; i++) {
			for (int j = i; j < cum.length; j++) {
				int res = cum[j] - (i > 0 ? cum[i - 1] : 0);
				if (res == 0 && a > 0)
					continue;
				if (res > 0 && a % res != 0)
					continue;
				Long tmp = null;
				if (res == 0)
					tmp = 1l * n * (n + 1) / 2;
				else
					tmp = mp.get(a / res);
				if (tmp == null)
					tmp = 0L;
				ans += tmp;
			}
		}
		out.println(ans);
		out.flush();
		out.close();
	}

	static class Scanner {
		BufferedReader bf;
		StringTokenizer st;

		public Scanner(InputStream i) {
			bf = new BufferedReader(new InputStreamReader(i));

		}

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

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

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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