Description

给定一个长度为 $n$ 的十进制数字序列。需要将该序列划分为一个或多个连续的子序列，使得每个子序列在被解释为十进制数时都能被给定的整数 $m$ 整除。

求不同的划分方式的数量，结果对 $10^9 + 7$ 取模。当判断两个划分是否不同的时候，我们只考虑子序列边界的位置，而不是数字本身。例如，划分 $2|22$ 和 $22|2$ 被认为是不同的。

Input Format

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n \leq 300000$, $1 \leq m \leq 1000000$) —— 序列的长度和除数。第二行包含一个恰好由 $n$ 个数字组成的字符串。

Output Format

输出一个整数，即不同划分的数量，对 $10^9 + 7$ 取模。

4 2
1246

4

4 7
2015

0

Hint

Central Europe Regional Contest 2015 Problem D。

题面翻译由 ChatGPT-4o 提供。