Sequence Partitioning Divisibility

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$. Note that when determining if two partitions are different, only the locations of subsequence boundaries are considered. For example, the partitions 2|22 and 22|2 are considered different.

inputFormat

The first line of input contains two integers n and m, where n is the number of digits in the sequence and m is the divisor. The second line contains a string of n decimal digits.

outputFormat

Output a single integer—the number of ways to partition the sequence such that every contiguous subsequence is divisible by m, taken modulo $10^9+7$.

sample

3 2
222

4