Problem Description

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 Format

The first line contains two integers \( n \) and \( m \) (\( 1 \leq n \leq 300000 \), \( 1 \leq m \leq 1000000 \)) – the length of the sequence and the divisor respectively. The second line contains a string consisting of exactly \( n \) digits.

Output Format

Output a single integer – the number of different partitions modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

4 2
1246

Sample Output #1

4

Sample Input #2

4 7
2015

Sample Output #2

0

Notes

Central Europe Regional Contest 2015 Problem D

见题面 Input 部分

见题面 Output 部分