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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main (String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader (inputStream);
		PrintWriter out = new PrintWriter (outputStream);
		TaskA solver = new TaskA ();
		solver.solve (1, in, out);
		out.close ();
	}
	
	static class TaskA {
		public void solve (int testNumber, InputReader in, PrintWriter out) {
/* WAY out of my range problem :( . Only one step is in my range, as sum in the rectangle (x1, y1, x2, y2) is
 * cs[x1, x2]·cs[y1, y2]. But after that no efficient way is found to proceed, so had to see editorial :(( ;
 * for every possible value(pv)<=a && a%pv==0 of sum I will have to find number of cs[x1,x2]=pv and cs[y1,y2]=
 * a/pv and ans+=their multiplication, in below implementation as i*i<=a so multiply it by 2 or 1 if i*i==a
 * as[x1,x2] and [y1,y2] can be swapped for the same result and I am not calculating all pvs to make complexity
 * o(sqrt(a)). There is a corner case when a is 0 which must be handled using inclusion exclusion principal:
 * Let f(0) be the number of substrings of the array that sum up to 0. So if 0 = a = sum(x1, x2)·sum(y1, y2),
 * we know that at least one of the factors must be 0. according to inclusion exclusion principle: ans is
 * (2.f(0)).(n.(n+1)/2)-f(0)^2 (this is the number of ways the first factor can get 0 while we don't care about
 * the second + the number of ways the second factor can get 0 while we don't care about the first - the
 * number of ways that both get 0).*/
			int a = in.nextInt ();
			String orstr = in.next ();
			int len = orstr.length ();
			byte[] arr = new byte[len+5];
			int[] cs = new int[len+5];
			HashMap<Integer, Integer> cntss = new HashMap<> ();//cntss = cnt of substrings that has sum (sum == index)
			for (int i = 0; i<len; i++) {
				arr[i] = (byte) (orstr.charAt (i)-'0');
				cs[i] = i == 0 ? arr[i] : cs[i-1]+arr[i];
			}
			for (int i = 0; i<len; i++) {
				for (int j = i; j<len; j++) {
					cntss.put (cs[j]-(i == 0 ? 0 : cs[i-1]), cntss.getOrDefault (cs[j]-(i == 0 ? 0 : cs[i-1]), 0)+1);
				}
			}
			if (a == 0) {
				out.println (
						cntss.getOrDefault (0, 0)*(long) len*(len+1)-cntss.getOrDefault (0, 0)*(long) cntss.getOrDefault (0, 0));
				return;
			}
			long ans = 0;
			for (int i = 1; i*i<=a; i++) {
				if (a%i == 0) {
					ans += cntss.getOrDefault (i, 0)*(long) cntss.getOrDefault (a/i, 0)*(long) (i*i == a ? 1 : 2);
				}
			}
			out.println (ans);
		}
		
	}
	
	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;
		
		public InputReader (InputStream stream) {
			reader = new BufferedReader (new InputStreamReader (stream), 32768);
			tokenizer = null;
		}
		
		public String next () {
			while (tokenizer == null || !tokenizer.hasMoreTokens ()) {
				try {
					String str;
					if ((str = reader.readLine ()) != null) tokenizer = new StringTokenizer (str);
					else return null;//to detect eof
				} catch (IOException e) {
					throw new RuntimeException (e);
				}
			}
			return tokenizer.nextToken ();
		}
		
		public int nextInt () {
			return Integer.parseInt (next ());
		}
		
	}
}

