P3245 [HNOI2016] 大数

小 B 有一个很大的数 $S$，长度达到了 $n$ 位；这个数可以看成是一个数字串，它可能有前导 $0$，例如 `00009312345`。小 B 还有一个素数 $p$。现在，小 B 提出了 $m$ 个询问，每个询问求 $S$ 的一个子串中有多少子串是 $p$ 的倍数（$0$ 也是 $p$ 的倍数）。例如 $S$ 为 `0077` 时，其子串 `007` 有 $6$ 个子串：`0,0,7,00,07,007`；显然 `0077` 的子串 `007` 有 $6$ 个子串都是素数 $7$ 的倍数。

无

无

#### 样例 1 解释 第一个询问问的是整个串，满足条件的子串分别有：`121121,2112,11,121,121`。 #### 数据范围 对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$2\le p\le 10^9$，$S$ 中只有数字字符，$p$ 为素数。