题目描述

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

他特别喜欢质数 $P$。他想知道在将这些非空（连续）子串视为十进制整数时，有多少个子串可以被 $P$ 整除。

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

计算这个数量，帮助高桥。

输入

第一行输入两个整数$N,P$

第二行输入一个字符串$S$

输出

输出可以被 $P$ 整除的非空（连续）子串的数量，作为一个十进制整数。

输出

4 3
3543

6

样例解释

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

3：可以被 3 整除。

35：不能被 3 整除。

354：可以被 3 整除。

3543：可以被 3 整除。

5：不能被 3 整除。

54：可以被 3 整除。

543：可以被 3 整除。

4：不能被 3 整除。

43：不能被 3 整除。

3：可以被 3 整除。

其中六个可以被 3 整除，所以输出 6。

4 2
2020

10

样例解释

这里 $S$ = 2020。

$S$ 有十个非空（连续）子串，所有这些子串都可以被 2 整除，所以输出 10。

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

20 11
33883322005544116655

68

提示

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $S$ 都是数字字符
• $|S|\ =\ N$
• $2\ \leq\ P\ \leq\ 10000$
• $P$ 是一个质数