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
// package april2020;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class C {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader scn = new FastReader();
		int a =scn.nextInt();
		String s = scn.next();
		int[] pre = new int[s.length()+1];
		pre[1] = s.charAt(0)-'0';
		for(int i=1;i<s.length();i++) {
			pre[i+1] = s.charAt(i)-'0'+pre[i];
		}
		
		long[] segs = new long[36000+1];
		for(int i = 1;i<pre.length;i++) {
			for(int j =0;j<i;j++) {
				int sum = pre[i]-pre[j];
				segs[sum]++;
			}
		}
//		for(int i =0;i<segs.length;i++) {
//			System.out.print(segs[i]+" "+((i>=10)?" ":""));
//		}
//		System.out.println();
//		for(int i =0;i<segs.length;i++) {
//			System.out.print(i+" ");
//		}
//		System.out.println();
		long ans = 0;
		for(int i=0;i<segs.length;i++) {
			if(i==0) {
				if(segs[i]>0&&a==0) {
					for(int j = 0;j<=36000;j++) {
						ans+=segs[i]*segs[j];
					}
				}
			}else {
				if(a%i==0) {
					if((a/i)<segs.length) {
						ans+=segs[i]*segs[a/i];
					}
				}
			}
		}
		System.out.println(ans);
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

}
