#P4421. [Cerc2015] Digit Division

[Cerc2015] Digit Division

题目描述

给出一个数字串,现将其分成一个或多个子串,要求分出来的每个子串能  mod M=0\bmod M =0。

将方案数  mod 109+7\bmod 10^9+7

输入格式

给出 N,MN,M。

接下来一行,一个数字串,长度为 N。

输出格式

如题

4 2
1246

4

数据规模与约定

对于 100%100\% 的数据,1≤N≤3×105,1≤M≤1061\le N\le 3\times 10^5,1\le M\le 10^6。