题目描述

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.

输入格式

The first line contains two integers n and m (1≤n≤300000, 1≤m≤1000000) – 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.

4 2
1246

4

4 7
2015

0

提示

Central Europe Regional Contest 2015 Problem D