CF364A.Matrix

You have a string of decimal digits s. Let's define b__ij = s__i·s__j. Find in matrix b the number of such rectangles that the sum b__ij 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.

你有一个十进制数字字符串 $ s $。定义 $ b_{ij} = s_i \cdot s_j $。在矩阵 $ b $ 中，找出满足如下条件的矩形个数：对每个这样的矩形，其所有单元格 $ (i, j) $ 对应的 $ b_{ij} $ 之和均等于 $ a $。

矩阵中的一个矩形由四个整数 $ (x, y, z, t) $（满足 $ x \leq y $，$ z \leq t $）确定。该矩形所包含的单元格为所有满足 $ x \leq i \leq y $、$ z \leq j \leq t $ 的 $ (i, j) $。

The first line contains integer a (0 ≤ a ≤ 109), the second line contains a string of decimal integers s (1 ≤ |s| ≤ 4000).

第一行包含整数 $a$（$0 ≤ a ≤ 10^9$），第二行包含一个十进制数字字符串 $s$（$1 ≤ |s| ≤ 4000$）。

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.

输出一个整数——即该问题的答案。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 格式说明符。推荐使用 cin、cout 流，或 %I64d 格式说明符。