题目描述

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

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

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

输入描述

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

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

输出描述

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

样例

2
102

5

2
12342

11

样例 1 解释

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