问题描述

梦梦随机生成了一个数字字符串 $S$。

熊熊给出了一个质数 $p$，梦梦想知道字符串 $S$ 有多少个子串构成的数字，忽视前导零后，恰好是 $p$​ 的倍数。

例如对于字符串 $S=172146$，其子串 $S[2:4]$ 构成的数字为 $721$。

输入格式

第一行包含一个字符串 $S$，由数码 0 至 9 构成。

第二行给出一个正整数，表示 $p$。

输出格式

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

样例输入1

3543
3

样例输出1

6

样例解释1

$S[1:1],S[4:4],S[1:3],S[2:4],S[2:3],S[1:4]$ 均为合法的子串。

样例输入2

172146
7

样例输出2

4

样例解释2

$S[2:4],S[2:2],S[3:4],S[4:5]$ 均为合法的子串。

样例输入3

123213890431421321
2

样例输出3

76

样例输入4

123215890431421321
5

样例输出4

15

样例输入5

12321589043142132112380921312389210389210289132189302189048902390841390824
97

样例输出5

27

评测数据规模

对于 $20\%$ 的数据，$p=2$。

对于另外 $20\%$ 的数据，$p=5$。

对于所有测评数据，$1 \leq |S| \leq 10^5,2 \leq p \leq 998244353$。