Problem Description

Given a string \( S \) of length \( L \) consisting of digits \( 0 \) to \( 9 \). It is easy to see that there are \( \frac{L(L + 1)}{2} \) contiguous substrings. If a substring, interpreted as a number (leading zeros are allowed), is a multiple of \( p \), then this substring is called a relative number of the string \( S \) with respect to \( p \).

For example, if the string \( S \) is "12342" and \( p \) is 2, among the 15 contiguous substrings, the relative numbers are "12", "1234", "12342", "2", "234", "2342", "34", "342", "4", "42", and "2" for a total of 11. Note that "2" appears twice, but since its positions in \( S \) are different, they are considered different relative numbers.

Now, given the string \( S \) and the positive integer \( p \), can you calculate how many relative numbers there are?

Input Format

The first line of input contains a positive integer \( p \). It is guaranteed that \( 2 \leq p \leq 128 \).
The second line of input contains a string \( S \) of length \( L \). It is guaranteed that \( 1 \leq L \leq 10^6 \).

Output Format

Output a single integer on one line, representing the answer.

Sample Input and Output

Sample Input #1

2
102

Sample Output #1

5

Sample Input #2

2
12342

Sample Output #2

11

Notes

Explanation of Sample 1

The 5 relative numbers are 10, 102, 0, 02, and 2.

见题面 Input 部分

见题面 Output 部分