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
/*
    Date         : Nov 27, 2013
    Problem Name : matrix
    Location     : http://codeforces.com/contest/365/problem/C
    Algorithm    : 
    Status       : coding
    CodingTime   : 1:23-
    ReadingTime  :
*/

import java.util.*;
import java.io.*;
public class Main {
    static BufferedReader reader 
		= new BufferedReader(new InputStreamReader(System.in));       

    public static void main(String[] args){
        int i, j;
        String inp = getLine();
        int a = Integer.parseInt(inp);
        inp = getLine();
        char[] s = inp.toCharArray();
        int n = s.length; 
        int[] partial = new int[n]; // partial [i] = s[0] + ... + s[i]
        partial[0] = s[0] - '0';
        for (i = 1; i < n; i++)
            partial[i] = partial[i-1] + s[i] - '0';


        long[] cnt = new long[40000]; // cnt[i] shows how many partial sums of s are equal to i
        for (int from = 0; from < n; from++)
            for (int till = from; till < n; till++)
                if (from > 0){
                    cnt[partial[till] - partial[from - 1]] ++;
                } else {
                    cnt[partial[till]] ++;
                }

        long acc = 0; // answer
        for (i = 1; i < 40000; i++)
            if (a % i == 0 && a / i < 40000){
                acc += cnt[i] * cnt[a / i];
            }
        if (a == 0)
            acc = acc * 2 + cnt[0] * cnt[0];

        System.out.println(acc);
    }

	static String getLine(){
		try { 
			return reader.readLine().trim();
		} catch (Exception e){}
		return null;
	}
}

