Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2021 05:50:51 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|