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 109+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.
The first line contains two integers n and m (1≤n≤3⋅105,1≤m≤106) — the length of the sequence and the divisor respectively. The second line contains a string consisting of exactly n digits.
Output a single integer — the number of different partitions modulo 109+7.