给定一串长度为 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，你能计算出有多少个亲朋数吗？

输入的第一行，包含一个正整数 p。约定 2 ≤ p ≤ 128。

输入的第二行，包含一个长为 L 的数字串S。约定 1 ≤ L ≤ 10^6 。

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

【样例解释 1】

5 个亲朋数，分别为 “10”、“102”、“0”、“02”、“2” 。

GESP样题六级

GESPGESP样题