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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Set;

public class A {
	static InputReader in;
	static PrintWriter out;

	public static void main(String[] args) throws Exception {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);

		int a = in.nextInt();
		String s = in.nextToken();
		int[] arr = new int[s.length()];
		for (int i = 0; i < s.length(); i++) {
			arr[i] = s.charAt(i) - '0';
		}

		// how many <i,j> sum = k
		long[] count = new long[4000 * 10];
		int numPair = 0;
		Set<Integer> set = new HashSet();
		for (int l = 0; l < arr.length; l++) {
			int sum = 0;
			for (int r = l; r < arr.length; r++) {
				sum += arr[r];
				count[sum]++;
				set.add(sum);
				numPair++;
			}
		}

		out.println(myans(arr, set, a, count, numPair));
		out.close();
	}

	static long myans(int[] arr, Set<Integer> set, int a, long[] count,
			int numPair) {
		long ans = 0;
		if (a == 0) {
			ans = 2 * count[0] * numPair - count[0] * count[0];
		} else {
			for (int i : set) {
				if(i==0)continue;
				if (a % i == 0) {
					int other = a / i;
					if(set.contains(other))
						ans += count[i] * count[other];
				}

			}
		}
		return ans;
	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String nextToken() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}

		public static boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}