题目描述

Takahashi has a string $S$ of length $N$ consisting of digits from 0 through 9.

He loves the prime number $P$. He wants to know how many non-empty (contiguous) substrings of $S$ - there are $N \times (N + 1) / 2$ of them - are divisible by $P$ when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in $S$ are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

高桥有一个长度为 $N$ 的字符串 $S$ ，由从 0 到 9 的数字组成。

他喜欢质数 $P$ 。他想知道 $S$ 的非空（连续）子串 $N \times (N + 1) / 2$ 有多少个。- 有 $N \times (N + 1) / 2$ 个--如果看作以十为底数的整数，则可以被 $P$ 整除。

在这里，以 "0 "开头的子串也算数，而且从 $S$ 的不同位置开始的子串也要加以区分，即使它们作为字符串或整数是相等的。

计算这个计数来帮助高桥。

输入格式

输入内容按以下格式标准输入：

$N$ $P$
$S$

输出格式

打印 $S$ 的非空（连续）子串中，能被 $P$ 整除（以十为基数）的个数。

样例 #1

样例输入 #1

4 3
3543

样例输出 #1

6

样例 #2

样例输入 #2

4 2
2020

样例输出 #2

10

样例 #3

样例输入 #3

20 11
33883322005544116655

样例输出 #3

68

说明

数据规模与约定

• $1 \leq N \leq 2 \times 10^5$
• $S$ 由数字组成。
• $|S| = N$
• $2 \leq P \leq 10000$
• $P$ 是质数。

样例 $1$ 解释

此处 $S$ = 3543。 $S$ 有十个非空（连续）子串：

• 3`：可被 $3$ 整除。

• 35`：不能被 $3$ 整除。

• 354`:能被 $3$ 整除。

• 3543`:可以被 $3$ 整除。

• 5`:不能被 $3$ 整除。

• 54`:能被 $3$ 整除。

• 543`:能被 $3$ 整除。

• 4`：不能被 $3$ 整除。

• 43`:不能被 $3$ 整除。

• 3`:不能被 $3$ 整除。

其中 6 个能被 $3$ 整除，因此打印 $6$ 。

样例 $2$ 解释

这里 $S$ = 2020。 $S$ 有 10 个非空（连续）子串，它们都能被 $2$ 整除，因此打印 $10$ 。

请注意，以 "0 "开头的子串也算数。