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

public class Solution{
    
    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; 
        } 
    }
        
	public static void main (String[] args) throws Exception{
	    FastReader sc = new FastReader();
	    
	    long a = sc.nextLong();
	    
	    char[] line = sc.nextLine().toCharArray();
	    int n = line.length;
	    long[] arr = new long[n+1];
	    
	    for(int i=0;i<n;i++){
	        line[i] -= '0';
	        arr[i+1] = (long)(line[i]);
	        arr[i+1] += arr[i];
	    }
	    
	    HashMap<Long, Long> map = new HashMap<Long, Long>();
	    //ArrayList<Long> vlist = new ArrayList<Long>();
	    
	    for(int i=1;i<=n;i++)
	        for(int j=i;j<=n;j++){
	            long key = arr[j]-arr[i-1]; 
	            //vlist.add(key);
	            Long val =  map.get(key);
	            if(val==null) val=0L;
	            map.put(key, val+1L);
	        }
	         
	    long ans = 0;
		for (int i = 0; i < line.length; i++)
		{
			long sum = 0;
			for (int j = i; j < line.length; j++)
			{
				sum += line[j];
				if (sum == 0 && a == 0)
					ans += (line.length)*(line.length+1)/2;
				else if (sum != 0 && a % sum == 0)
				{
					Long occ = map.get(a/sum);
					if (occ != null)
						ans += occ;
				}
			}
		}
		System.out.println(ans);      
	         
	   /*      
	    //System.out.println(vlist);
	    
	    if(a==0L){
	        Long val = map.get(0L);
	        if(val==null) val=0L;
	        System.out.println( (val*val) );
	        return;
	    }
	    
	    long count=0;
	    for(long val : vlist){
	        if(a%val==0 && map.containsKey(a/val))
	            count+=map.get(a/val);
	    }
	    
	    System.out.println(count);*/
	}
}