問題文

高橋君は 0 から 9 までの数字から成る長さ $N$ の文字列 $S$ を持っています。

素数 $P$ が好きな高橋君は、$S$ の空でない連続する部分文字列 $N \\times (N + 1) / 2$ 個のうち、十進表記の整数と見なした際に $P$ で割り切れるものの個数を知りたくなりました。

ただし部分文字列は先頭が 0 であっても良いものとし、文字列として等しい場合や、整数と見なした際に等しい場合も、部分文字列の $S$ 内の位置で区別します。

高橋君のためにこの個数を計算してください。

制約

• $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 です。$S$ の空でない連続する部分文字列は次の $10$ 個があります。

• 3 は $3$ で割り切れる。

• 35 は $3$ で割り切れない。

• 354 は $3$ で割り切れる。

• 3543 は $3$ で割り切れる。

• 5 は $3$ で割り切れない。

• 54 は $3$ で割り切れる。

• 543 は $3$ で割り切れる。

• 4 は $3$ で割り切れない。

• 43 は $3$ で割り切れない。

• 3 は $3$ で割り切れる。

このうち $3$ で割り切れるものは $6$ 個であるので、$6$ を出力してください。

入力例 2

4 2
2020

出力例 2

10

$S$ = 2020 です。$S$ の空でない連続する部分文字列は $10$ 個ありますが、その全てが $2$ で割り切れるので $10$ を出力してください。

先頭が 0 である部分文字列も許容されることに注意してください。

入力例 3

20 11
33883322005544116655

出力例 3

68