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 static java.lang.Math.*;
public class A {
	void run() {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		char[] c = sc.next().toCharArray();
		int n = c.length;
		int[] s = new int[n];
		for (int i = 0; i < n; ++i) {
			s[i] = c[i] - '0';
		}

		//s = new int[2500];
		//a = 0;
		//n = 2500;

		// partial sums
		int[] t = new int[n+1];
		for (int i = 0; i < n; ++i) {
			t[i+1] = t[i] + s[i];
		}

		List<Integer> d = new ArrayList<Integer>();
		for (int i = 0; i < n; ++i) {
			for (int j = i+1; j <= n; ++j) {
				int x = t[j] - t[i];
				// use a sanity check for a filter (for the memory)
				// check there is a solution to x * y == a
				if (a == 0) {
					if (x == 0)
						d.add(x);
				} else {
					if (x > 0 && a % x == 0)
						d.add(x);
				}
			}
		}
		Collections.sort(d);
		Deque<Integer> deque = new ArrayDeque<Integer>(d);

		List<Integer> val = new ArrayList<Integer>();
		List<Integer> num = new ArrayList<Integer>();
		while (deque.size() > 0) {
			int v = deque.pop();
			int nu = 1;
			while (deque.size() > 0 && deque.peek() == v) {
				deque.pop();
				++nu;
			}
			val.add(v);
			num.add(nu);
		}

		int lo = 0;
		int hi = val.size()-1;
		long ans = 0;

		while (lo < val.size() && hi >= 0) {
			int p = val.get(lo) * val.get(hi);
			if (p < a) {
				++lo;
			} else if (p == a) {
				ans += (long) num.get(lo) * num.get(hi);
				++lo;
				--hi;
			} else {
				--hi;
			}
		}

		// aaaah zeros
		if (a == 0) {
			long num_z = 0;
			if (val.size() > 0 && val.get(0) == 0) {
				num_z = num.get(0);
			}
			ans = num_z * n * (n+1) - num_z * num_z;
		}

		p("%d\n", ans);
	}
	void p(String f,Object...p) {
		System.out.printf(f, p);
	}
	public A() {}
	public static void main(String[] args) {
		new A().run();
	}
}
