题目描述

Takahashi 有一个长度为 $N$ 且由数字 0 到 9 组成的字符串 $S$。

他喜欢素数 $P$。他想知道在将 $S$ 视为十进制整数时，有多少个非空（连续的）子串能被 $P$ 整除。

这里，以 0 开头的子串也计入在内，并且来自 $S$ 的不同位置的子串是不同的，即使它们作为字符串或整数相等。

请计算这个数量，帮助 Takahashi。

约束条件

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

输入

从标准输入读取输入数据，输入格式如下：

$N$ $P$ $S$

输出

打印在将 $S$ 视为十进制整数时能被 $P$ 整除的非空（连续的）子串的数量。

示例输入 1

4 3
3543

示例输出 1

6

这里 $S$ = 3543。有十个非空（连续的）子串：

• 3：能被 $3$ 整除。

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

• 354：能被 $3$ 整除。

• 3543：能被 $3$ 整除。

• 5：不能被 $3$ 整除。

• 54：能被 $3$ 整除。

• 543：能被 $3$ 整除。

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

• 43：不能被 $3$ 整除。

• 3：能被 $3$ 整除。

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

示例输入 2

4 2
2020

示例输出 2

10

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

注意，以 0 开头的子串也计入在内。

示例输入 3

20 11
33883322005544116655

示例输出 3

68