题目描述

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

将方案数 $\bmod 10^9+7$

输入格式

给出 $N,M$。

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

输出格式

如题

4 2
1246

4

数据规模与约定

对于 $100\%$ 的数据，$1\le N\le 3\times 10^5,1\le M\le 10^6$。