Digit Division

Count the ways to split a digit string into contiguous blocks so each block is divisible by m, modulo 1e9+7.

Medium7Dynamic programmingMathHash mapNo attempts yetTime limit1sMemory limit512 MB

Description

Examples2

Problem

You are given a sequence of $n$ decimal digits. Split the sequence into one or more contiguous blocks so that every block, read as a decimal number, is divisible by the integer $m$ .

Count how many such splits exist and print the count modulo $10^9 + 7$ . Two splits are different when their boundary positions differ, not when their digits differ. For example, 2|22 and 22|2 are two different splits.

Input

The first line contains the length $n$ of the sequence and the divisor $m$ ( $1 \le n \le 300000$ , $1 \le m \le 1000000$ ).

The second line contains a string of exactly $n$ digits. The string may start with a zero.

Output

Print the number of splits modulo $10^9 + 7$ on one line.