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.</p>

Find the number of different such partitions modulo 10⁹ + 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 ≤ 300 000, 1 ≤ m ≤ 1 000 000) – 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 10⁹ + 7.

예제 입력 1

4 2
1246

예제 출력 1

4

예제 입력 2

4 7
2015

예제 출력 2

0