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

public class Main {

	public static void main(String[] args) throws Throwable {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[] a = sc.nextLine().toCharArray(); 
		int[] cnt = new int[10];
		for (int i = 0; i < a.length; i++) 
			++cnt[a[i]-'0'];
		int[] sum = new int[a.length];
		sum[0] = a[0]-'0';
		for(int i = 1;i<sum.length;i++)sum[i]=sum[i-1]+(a[i]-'0');
		long ans = 0;
		HashMap<Long,Long>map = new  HashMap<>();
		map.put(0l,0l);
		for(int len = 0;len<a.length;len++)
		{
			for(int i = len;i<a.length;i++)
			{
				long window = sum[i] - (i-len>0?sum[i-len-1]:0);
				if(!map.containsKey(window))
					map.put(1l*window, 0l);
				map.put(1l*window,1l+map.get(window));
			}
		}
		long total = 1l*(a.length+1)*(a.length)/2;
		for(int i = 0; i < a.length;i++)
		{
			for(int j= i;j<a.length;j++)
			{
				long curSum = sum[j] - (i-1>=0?sum[i-1]:0);
				if(n==0)
				{
					if(curSum==0)ans+=total;
					else ans += map.get(0l);
				}
				else if(curSum!=0 && n%curSum==0)
				{
					Long other = map.get(n/curSum);
					if(other!=null)ans+=other;
				}
			}
		}
		System.out.println(ans);
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public int[] nexIntArray() throws Throwable
		{
			st = new StringTokenizer(br.readLine());
			int[] a = new int[st.countTokens()];
			for(int i = 0; i < a.length;i++)a[i]=nextInt();
			return a;
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}
}
