2728: T3-质数的倍数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：1
题目描述
梦梦随机生成了一个数字字符串 $S$。
熊熊给出了一个**质数** $p$，梦梦想知道字符串 $S$ 有多少个子串构成的数字，**忽视前导零后**，恰好是 $p$ 的倍数。
例如对于字符串 $S=172146$，其子串 $S[2:4]$ 构成的数字为 $721$。
熊熊给出了一个**质数** $p$，梦梦想知道字符串 $S$ 有多少个子串构成的数字，**忽视前导零后**，恰好是 $p$ 的倍数。
例如对于字符串 $S=172146$，其子串 $S[2:4]$ 构成的数字为 $721$。
输入
第一行包含一个字符串 $S$，由数码 `0` 至 `9` 构成。
第二行给出一个正整数，表示 $p$。
第二行给出一个正整数，表示 $p$。
输出
输出一行，包含一个整数，表示答案。
样例输入 复制
3543
3样例输出 复制
6提示
### 样例解释1
$S[1:1],S[4:4],S[1:3],S[2:4],S[2:3],S[1:4]$ 均为合法的子串。
### 样例输入2
```text
172146
7
```
### 样例输出2
```text
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$。
$S[1:1],S[4:4],S[1:3],S[2:4],S[2:3],S[1:4]$ 均为合法的子串。
### 样例输入2
```text
172146
7
```
### 样例输出2
```text
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$。