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.IOException;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author karan173
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    public void solve(int testNumber, FastReader in, PrintWriter out)
    {
        HashMap<Long, Integer> map = new HashMap<Long, Integer> ();
        long a = in.nl ();
        char s[] = in.ns ().toCharArray ();
        int n = s.length;
        long sum[] = new long[n+1];
        long ans = 0;
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
        {
              sum[i] = sum[i - 1] + (s[i-1] - '0');
        }
        //out.println (Arrays.toString (sum));
        if (a == 0)
        {
            long cnt0 = 0;
            long cntOthers = 0;
            for (int i = 1; i <= n; i++)
            {
                for (int j = i; j <= n; j++)
                {
                    long s1 = sum[j] - sum[i-1];
                    if (s1 == 0)
                    {
                        cnt0++;
                    }
                    else
                    {
                        cntOthers++;
                    }
                }
            }
            for (int i = 1; i <= n; i++)
            {
                for (int j = i; j <= n; j++)
                {
                    long s1 = sum[j] - sum[i-1];
                    if (s1 == 0)
                    {
                        ans += cnt0 + cntOthers;
                    }
                    else
                    {
                        ans += cnt0;
                    }
                }
            }
            out.println (ans);
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                long s1 = sum[j] - sum[i-1];
                if (s1 != 0 && a % s1 == 0)
                {
                    //now add
                    if (map.containsKey (s1))
                    {
                        map.put (s1, map.get (s1) + 1);
                    }
                    else
                    {
                        map.put (s1, 1);
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                long s1 = sum[j] - sum[i-1];
                if (s1 != 0 && a % s1 == 0)
                {
                    long div = a / s1;
                    if (map.containsKey (div))
                    {
                        ans += map.get (div);
                    }
                }
            }
        }
//        out.println (map);
        out.println (ans);
    }
}

class FastReader
{

    public InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream)
    {
        this.stream = stream;
    }

    public int read()
    {
        if (numChars == -1)
        {
            throw new InputMismatchException ();
        }
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read (buf);
            } catch (IOException e)
            {
                throw new InputMismatchException ();
            }
            if (numChars <= 0)
            {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public long nl()
    {
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read ();
        }
        long res = 0;
        do
        {
            if (c < '0' || c > '9')
            {
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        } while (!isSpaceChar (c));
        return res * sgn;
    }

    public String ns()
    {
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        StringBuilder res = new StringBuilder ();
        do
        {
            res.appendCodePoint (c);
            c = read ();
        } while (!isSpaceChar (c));
        return res.toString ();
    }

    public boolean isSpaceChar(int c)
    {
        if (filter != null)
        {
            return filter.isSpaceChar (c);
        }
        return isWhitespace (c);
    }

    public static boolean isWhitespace(int c)
    {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}
