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 cf213;

import java.util.*;
import java.io.*;

public class A {
	FastScanner in;
	PrintWriter out;

	public void solve() throws IOException {
		int n = in.nextInt();
		String s = in.next();
		long m = s.length();
		
		
		
		if (n == 0) {
			long ans = 0;
			long l = 0;
			long count = 0;
			for (int i = 0; i < m; i++) {
				if ((s.charAt(i) - '0') == 0) {
					l++;
					count += l;
				} else {
					l = 0;
				}
			}
			ans = (count * (m * (m + 1) / 2)) * 2 - count * count;
			System.out.println(ans);
			return;
			
		}
		
		
		HashMap<Long, Long> divisors = new HashMap<Long, Long>();
		for (long i = 1; i < Math.sqrt(n) + 1; i++) {
			if ((n % i) == 0) {
				divisors.put((long)i, 0L);
				divisors.put((long)(n / i), 0L);
			}
		}
		long[] sums = new long[(int)m + 1];
		sums[0] = 0;
		for (int i = 1; i <= m; i++) {
			sums[i] = sums[i - 1] + (s.charAt(i - 1) - '0');
		}
		for (int i = 0; i < m; i++) { 
			for (int j = i + 1; j <= m; j++) {
				long cur = sums[j] - sums[i];
				if (divisors.containsKey(cur)) {
					divisors.put(cur, divisors.get(cur) + 1);
				}
			}
		}
		long ans = 0;
		for (long i = 1; i < Math.sqrt(n) + 1; i++) {
			if ((n % i) == 0) {
				if ((i * i <= n)) {
					if ((i != (n / i))) {
						ans += divisors.get(i) * divisors.get(n / i) * 2;
					} else {
						ans += divisors.get(i) * divisors.get(i);
					}
				}
			}
		}
		System.out.println(ans);
	}

	public void run() {
		try {
			in = new FastScanner(System.in);
			out = new PrintWriter(new File("object.out"));

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

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

	public static void main(String[] arg) {
		new A().run();
	}
}