如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
看到题的第一眼我是考虑 $\text{dp}$ 的，太菜没想到正解，设 $f_i$ 为在第 $i$ 位后分割的方案数，则有：
其中 $a_{i,j}$ 表示从第 $i$ 位到第 $j$ 位组成的数字。
显然 $\mathrm{O(n^2)}$ 的 $\text{dp}$ 不能通过此题，考虑如何优化。
我们可以在 $\mathrm{O(n)}$ 的时间复杂度内预处理出所有最小的能被 $m$ 整除的区间，我们只需要考虑每个分割点即可。
这时我们可以发现，对于每个分割点，都可以选择分割或不分隔，由于
\[a \operatorname{mod}m=0,b\operatorname{mod}m=0\] \[\text{有} (a\times10^k+b) \operatorname{mod}m=0\]所以我们可以在所有分割点中选择任意几个分割，这方案数其实就是 $2^k$，$k$ 为分割点数量。
Q：何时无解？
A：当整体无法被 $m$ 整除时，则无解。
代码
#include<cstdio>
int n,m,aa,k;
char c[300010];
int pow(int x,int y){
int res(1);
while(y){
if(y&1) res=1ll*res*x%1000000007;
x=1ll*x*x%1000000007;
y>>=1;
}
return res%1000000007;
}
int main(){
scanf("%d%d%s",&n,&m,c);
for(int i=0;i<n;i++){
aa=(aa*10%m+c[i]-'0')%m;
if(aa==0)++k;
}
if(aa) puts("0");
else printf("%d\n",pow(2,k-1));
return 0;
}