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
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import bisect

## プロトタイプ
def matrix ():
    ## 入力
    # 標準入力を取得
    a = raw_input()
    s = raw_input()
    # 入力を処理に合った形に変換
    rect_sum    = int(a)          # 矩形領域内の合計値
    numbers     = map(int,s)      # 数値列
    len_numbers = len(s)          # 数値列の長さ

    ## 一辺の合計値リストを作成
    # 合計値をインデックスにしたテーブルを作成．中身は出現数．
    edge_sums = [0] * (4000 * 9)
    # 端から端までの部分和を算出しつつ，テーブルに登録
    partial_sums = []
    psum = 0
    for num in numbers:
        psum += num
        partial_sums.append(psum)
        edge_sums[psum] += 1
    max_edge_sums = psum
    # 残りの各合計値は，全体の部分和を基にして，端から順に値を引いていくことで算出．
    for index, left in enumerate(partial_sums):
        for right in partial_sums[index+1:]:
            edge_sums[right - left] += 1

    ## 一辺の相方となる，もう一辺の合計値の数を足していく
    if rect_sum != 0:
        # a が 0 でない場合，矩形の合計値は両辺の合計値の積となる
        # もう一辺の合計値を算出しつつ，出現回数を順に足していく
        answer = 0
        for index, value in enumerate(edge_sums[1:], 1):
            if rect_sum % index != 0:
                continue
            if (rect_sum / index > max_edge_sums):
                continue
            answer += edge_sums[rect_sum / index] * value
    else:
        # a が 0 の場合，一方が 0 であればよいので，
        # 全パターンから，両方が 0 でないパターンの総数を引けばよい
        num_all = sum(edge_sums)
        num_nonzero = sum(edge_sums[1:])
        answer = (num_all ** 2) - (num_nonzero ** 2)
    print answer
    return

if __name__ == '__main__':
    matrix()
