Problem10646--洛谷P10262 - [GESP六级] [样题]亲朋数

10646: 洛谷P10262 - [GESP六级] [样题]亲朋数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

给定一串长度为 $L$、由数字 $0\sim 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$ ,你能计算出有多少个亲朋数吗?

Input

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

Output

输出一行一个整数表示答案。

Constraints

$5$ 个亲朋数,分别 $10$、$102$、$0$、$02$、$2$。

Sample 1 Input

2
102

Sample 1 Output

5

Sample 2 Input

2
12342

Sample 2 Output

11

HINT

洛谷P10262

Source/Category