Matrix

1000ms

262144K

Description:

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.

Input:

The first line contains integer a (0 ≤ a ≤ 10⁹), 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.

Sample Input:

10
12345

Sample Output:

Sample Input:

16
439873893693495623498263984765

Sample Output:

Informação

Provedor Codeforces

Código CF364A