Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1106.

Problem Description

You are given a digit string $S$ of length $L$, consisting of digits $0 \sim 9$. It is easy to see that it has $\frac{L(L + 1)}2$ contiguous substrings in total. If the number represented by a substring (leading zeros are allowed) is a multiple of $p$, then this substring is called a “friendly substring” of the digit string $S$ with respect to $p$.

For example, if the digit string $S$ is “ $12342$ ” and $p = 2$, then among the $15$ contiguous substrings, the friendly substrings are “ $12$ ”, “ $1234$ ”, “ $12342$ ”, “ $2$ ”, “ $234$ ”, “ $2342$ ”, “ $34$ ”, “ $342$ ”, “ $4$ ”, “ $42$ ”, and “ $2$ ”, for a total of $11$. Note that “ $2$ ” appears $2$ times, but since they occur at different positions in $S$, they are counted as different friendly substrings.

Now, given the digit string $S$ and a positive integer $p$, can you compute how many friendly substrings there are?

Input Format

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

Output Format

Output one line containing one integer, representing the answer.

2
102

5

2
12342

11

Hint

Sample 1 Explanation

There are $5$ friendly substrings: $10$, $102$, $0$, $02$, and $2$.

Translated by ChatGPT 5