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^{9}$), 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.