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 3\cdot 10^5,1\le m\le 10^6)$ — 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$.

Examples