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


public class A213 {
    
public static void main(String [] argv) throws Exception{
        
        new A213().run(); 
    }
         
    int[] zs;
    void getZs(String s){
        int n=s.length();
        zs=new int[n+1];
        for(int i=0;i<n;i++)
                zs[i+1]=zs[i]+(s.charAt(i)-'0');
    }
     
    /*
    long getCnt(int val, int[] zs){
        int n=zs.length;
        long cnt=0;
        for(int i=1;i<n;i++)
            for(int j=0;j<i;j++)
                if(zs[i]-zs[j]==val)
                    cnt++;
        return cnt;
    }
    */
    
    long getCnt(int val, int[] zs){
        int n=zs.length;
        long cnt=0;
        for(int i=1;i<n;i++){
            int searchFor=zs[i]-val;
            int index=Arrays.binarySearch(zs,  0, i, searchFor);
            if(index>=0){
                int akt=index-1;
                while(akt>=0 && zs[akt]==searchFor){
                    cnt++;
                    akt--;
                }
                akt=index;
                while(akt<i && zs[akt]==searchFor){
                    cnt++;
                    akt++;
                }
            }
            
        }
        return cnt;
    }
    
    /*long getCnt(int val, int[] zs){
        //System.err.println(val+Arrays.toString(zs));
        int n=zs.length;
        long cnt=0;

        int akt=0;
        int last=0;
        int sum=0;
        while(akt<n){
            //System.err.println(akt+" "+last+" "+sum);
            if(sum<val){
                sum+=zs[akt];
                akt++;
            }
            if(sum>val){
                sum-=zs[last];
                last++;
            }
            if(sum==val){
                int cntOben=1;
                while(akt+1<n && zs[akt+1]==0){
                    akt++;
                    cntOben++;
                }
                int cntUnten=1;
                while(last<akt && zs[last]==0){
                    last++;
                    cntUnten++;
                }
                if(last==akt){
                    cnt+=cntUnten*(cntOben+1)/2;
                }
                else
                    cnt+=cntUnten*cntOben;
                //if(val==4) System.out.println(akt+" "+cntUnten+" "+cntOben);
                if(akt>=n) break;
                sum+=zs[akt];
                akt++;
                
                
                //if(val==4) System.out.println(zs[akt]+"  "+sum);
                akt++;
            }   
        }
        return cnt;
        
    }
   */ 
    long getAll(int a, int[] zs){
        if(a==0){
            long g=getCnt(0, zs);
            int n=zs.length-1;
            long res=g*n*(n+1)-g*g;
            return res;
        }
        
        long res=0;
        
        int i=1;
        while(i*i<=a){
            int j=a/i;
            if(a==i*j){
                long cnt1=getCnt(i, zs);
                long cnt2=getCnt(j, zs);
                //System.out.println(i+" "+j+" cnts "+cnt1+" "+cnt2);
                res+=cnt1*cnt2;
                if(i!=j)
                    res+=cnt1*cnt2;
            }
            i++;
        }
        return res;
    }
    
   
            void run() throws Exception{
                BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
                
                int a=Integer.parseInt(reader.readLine());
                String s=reader.readLine();
                getZs(s);
                System.out.println(getAll(a, zs));
                reader.close();
            }
            
            
             int[] getArray(String line){
                    String[] array=line.split(" ");
                    int[] res=new int[array.length];
                    for(int i=0;i<res.length;i++)
                        res[i]=Integer.parseInt(array[i]);
                    return res;
                  }
                 
                 void getArrays(int n, BufferedReader reader, int[]... ar) throws Exception{
                       for(int i=0;i<n;i++){
                           String[] ss=reader.readLine().split(" ");
                           for(int j=0;j<ss.length;j++)
                               ar[j][i]=Integer.parseInt(ss[j]);
                       }
                    }
}
