Problem M
Digit Division
We are given a sequence of $n$ decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer $m$.
Find the number of different such partitions modulo $10^9 + 7$. When determining if two partitions are different, we only consider the locations of subsequence boundaries rather than the digits themselves, e.g. partitions $2|22$ and $22|2$ are considered different.
Input
The first line contains two integers $n$ and $m$ $(1 \le n \le 300\, 000, 1 \le m \le 1\, 000\, 000)$ - the length of the sequence and the divisor respectively. The second line contains a string consisting of exactly $n$ digits.
Output
Output a single integer – the number of different partitions modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 1246 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 7 2015 |
0 |