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.*;
import java.util.*;

public class Main
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a = Integer.parseInt(br.readLine());
		char[] s = br.readLine().toCharArray();
		int[] dp = new int[s.length + 1];
		for(int i = 1; i <= s.length; ++i)
			dp[i] = dp[i - 1] + (s[i - 1] - '0');
		long[] sums = new long[s.length * 9 + 1];
		for(int i = 0; i < dp.length - 1; ++i)
			for(int j = i + 1; j < dp.length; ++j)
				++sums[dp[j] - dp[i]];
		long result = 0;
		if(a == 0)
		{
			for(int i = 0; i < sums.length; ++i)
				result += sums[i];
			result *= sums[0];
			result *= 2;
			result -= sums[0] * sums[0];
		}
		else
		{
			for(int i = 1; i < sums.length; ++i)
				if(a % i == 0 && a / i < sums.length)
					result += sums[i] * sums[a / i];
		}
		System.out.println(result);
	}
}



/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////

class FunLib
{
	public static long gcd(long a, long b)
	{
		if(b == 0)
			return a;
		return gcd(b, a % b);
	}
	
	public static int gcd(int a, int b)
	{
		if(b == 0)
			return a;
		return gcd(b, a % b);
	}
	
	public static long lcm(long a, long b)
	{
		return a / gcd(a, b) * b;
	}
	
	public static int[][] transpose(int[][] mat)
	{
		int r = mat.length;
		int c = mat[0].length;
		int[][] result = new int[c][r];
		for(int i = 0; i < c; ++i)
			for(int j = 0; j < r; ++j)
				result[i][j] = mat[j][i];
		return result;
	}
}

abstract class AbstractSegTree
{
	public AbstractSegTree(int aSize)
	{
		size = aSize;
		storage = new int[4 * size];
	}
	
	public int getVal(int index)
	{
		return getValHelper(0, 0, size - 1, index);
	}
	
	public void rangeSet(int lower, int upper, int val)
	{
		rangeSetHelper(0, 0, size - 1, lower, upper, val);
	}
	
	protected abstract int getValHelper(int node, int beg, int end, int index);
	protected abstract void rangeSetHelper(int node, int beg, int end, int lower, int upper, int val);
	protected int[] storage;
	protected int size;
}


class Trie
{
	public Trie()
	{
		currentNode = root;
	}
	
	public void reset()
	{
		currentNode = root;
	}
	
	public void add(String word)
	{
		currentNode = root;
		for(int i = 0; i < word.length(); ++i)
		{
			// Only upper case characters
			int nodeIndex = word.charAt(i) - 'A';
			if(currentNode.children[nodeIndex] == null)
				currentNode.children[nodeIndex] = new Node();
			currentNode = currentNode.children[nodeIndex];
		}
		currentNode.isWord = true;
		currentNode = root;
	}
	
	public boolean feed(char c)
	{
		if(currentNode.children[c - 'A'] == null)
			return false;
		currentNode = currentNode.children[c - 'A'];
		return true;
	}
	
	public boolean isCurrentWord()
	{
		return currentNode.isWord;
	}
	
	private static class Node
	{
		public boolean isWord;
		// Only upper case characters
		public Node[] children = new Node[26];
	}
	
	private Node root = new Node();
	private Node currentNode;
}