No tag edit access

A. Matrix

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

10

12345

Output

6

Input

16

439873893693495623498263984765

Output

40

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/23/2018 21:59:31 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|