Hide

Problem K
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

Please log in to submit a solution to this problem

Log in