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.lang.reflect.Array;
import java.util.*;
import static java.lang.Integer.min;
import static java.lang.Long.max;

public final class Main {
        static FastScanner in=new FastScanner();
        static PrintWriter out=new PrintWriter(System.out);

        /*
        Never use sorting on 1-indexed array! or be very careful about negative values and stuff
        read the statement carefully!
        What about corner cases a=0?
        */
        public static void main(String[]args) {
                int a=in.nextInt();
                String s=in.next();
                int n=s.length();
                Map<Integer,Integer>map=new HashMap<>();
                for (int i=0;i<n;i++){
                        int sum=0;
                        for (int j=i;j<n;j++){
                                sum+=s.charAt(j)-'0';
                                map.put(sum, map.getOrDefault(sum, 0) + 1);
                        }
                }

                long ans=0;
                for (int i=0;i<n;i++){
                int sum=0;
                for (int j=i;j<n;j++){
                        sum+=s.charAt(j)-'0';

                        if(sum==0){
                                if(a==0)ans+=(long)n*(n+1)/2;
                        }
                        if(sum!=0&&a%sum==0){
                                ans+=map.getOrDefault(a/sum,0);
                        }
                }
        }


                out.println(ans);
                out.close();
        }




        static long lcm(long a,long b, long c){
                return lcm(a,lcm(b,c));
        }
        static long lcm(long a,long b){
                return a*b/gcd(a,b);
        }
        static long gcd(long a,long b) {
                if (a == 0) return b;
                return gcd(b%a,a);
        }
        static void printArray(long[]a,int m){
                for (int i=m;i<a.length+m;i++)out.print(a[i]+" ");
                out.println();
        }
        static void printArray(int[]a,int m){
                for (int i=m;i<a.length+m;i++)out.print(a[i]+" ");
                out.println();
        }
        static void printArray(String[]a,int m){
                for (int i=m;i<a.length+m;i++)out.print(a[i]+" ");
                out.println();
        }
        static void printArray(double[]a,int m){
                for (int i=m;i<a.length+m;i++)out.print(a[i]+" ");
                out.println();
        }
        static void printArray(boolean[]a,int m){
                for (int i=m;i<a.length+m;i++)out.print(a[i]+" ");
                out.println();
        }
        static class Pair implements Comparable<Pair>{
                int first,second;
                public Pair(int a,int b) {
                        first=a;
                        second=b;
                }
                @Override
                public int compareTo(Pair o) {
                        return first-o.first;
                }
        }
        static class FastScanner{
                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st=new StringTokenizer("");
                String next(){
                        while(!st.hasMoreTokens())
                                try{
                                        st=new StringTokenizer(br.readLine());
                                }catch(IOException e){
                                        e.printStackTrace();
                                }
                        return st.nextToken();
                }
                int nextInt() {
                        return Integer.parseInt(next());
                }
                int[] nextArray(int n,int m) {
                        int[] a=new int[n+m];
                        for (int i=m;i<n+m;i++)a[i]=nextInt();
                        return a;
                }
                long nextLong() {
                        return Long.parseLong(next());
                }
                double nextDouble() {
                        return Double.parseDouble(next());
                }
        }
}