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.util.*;
import java.math.*;
import java.text.DecimalFormat;
import java.text.NumberFormat;
 

@SuppressWarnings("unchecked")
public class Main {
      
    int mod = 1000000007;

    public class SegmentTree{

       int n; long[] tree;

       SegmentTree(long[] arr){

          this.n = arr.length; 
          this.tree = new long[2 * n];

          for(int i = n; i < 2 * n; i++) this.tree[i] = arr[i - n];
          for(int i = n - 1; i >= 1; i--) this.tree[i] = gcd(this.tree[2 * i], this.tree[2 * i + 1]);
       
       }

       public long query(int l, int r){
          
          l = l + n; 
          r = r + n;
          long res = tree[l];

          while(l < r){

              if(l % 2 == 1) res = gcd(res, tree[l++]); 
              if(r % 2 == 1) res = gcd(res, tree[--r]);
              l /= 2; r /= 2;
          }

          return res;
       }

       public void update(int idx, long v){
          
          idx += n; this.tree[idx] = v;
          while(idx > 1){
             idx /= 2;
             this.tree[idx] = Math.max(this.tree[2 * idx], this.tree[2 * idx + 1]);
          }
       }


    }

    public void solve() throws IOException{
    
         long a = in.nextLong();
         String str = in.next();
         int n = str.length();
         long[] cumsum = new long[n + 1];

         for(int i = 1; i <= n; i++) cumsum[i] = cumsum[i - 1] + (str.charAt(i - 1) - '0');

         long ans = 0;
         HashMap<Long, Long> map = new HashMap<>();

         for(int i = 0; i < n; i++){
            for(int j = i + 1; j <= n; j++){
               long side = cumsum[j] - cumsum[i];
               if(a == 0 ||(side > 0 && a % side == 0)) map.put(side, map.getOrDefault(side, 0L) + 1);
           }
         }

         if(a == 0 && map.containsKey(0L)){
               for(long num : map.keySet()){
                  if(num == 0) continue;
                  ans += 2 * map.get(0L) * map.get(num);
               }
               ans += map.get(0L) * map.get(0L);
         }else{
            for(long num: map.keySet()){
               ans += map.get(num) * map.getOrDefault(a / num, 0L);
            }
         }
         out.println(ans);
    } 




    FastScanner in;
    PrintWriter out;
    
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    public class Pair<A, B>{
        public A x; 
        public B y;

        Pair(A x, B y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!x.equals(pair.x)) return false;
            return y.equals(pair.y);
        }

        @Override
        public int hashCode() {
            int result = x.hashCode();
            result = 31 * result + y.hashCode();
            return result;
        }

    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}
