背景

GESP六级样题

描述

给定一串长度为$L$、由数字 $0-9$ 组成的数字串$S$。容易知道，它的连续子串共有$\frac {L(L+1)} {2}$个。如果某个子串对应的数（允许有前导零）是$p$的倍数，则称该子串为数字串$S$对于$p$的亲朋数。

例如，数字串$S$为“12342”、$p$为 2，则在 15 个连续子串中，亲朋数有“12”、“1234”、“12342”、“2”、“234”、“2342”、“34”、“342”、“4”、“42”、“2”等共 11 个。注意其中“2”出现了 2 次，但由于其在$S$中的位置不同，记为不同的亲朋数。

现在，告诉你数字串$S$和正整数$p$，你能计算出有多少个亲朋数吗？

格式

输入

输入的第一行，包含一个正整数𝑝。约定$2 ≤ p ≤ 128$。 输入的第二行，包含一个长为$L$的数字串$S$。约定$1 ≤ L ≤ 10^6$。

输出

输出一行，包含一个正整数$C$，表示亲朋数的个数。

样例

2
102

5

【样例解释 1】 5 个亲朋数，分别为“10”、“102”、“0”、“02”、“2”。

2
12342

11

限制

时间限制：1.0s 内存限制：128.0MB