Задачи
Разбиение цифр
Разбиение цифр
Задана последовательность из $n$ десятичных цифр. Разбейте ее на несколько (одну или более) последовательностей рядом стоящих цифр так, чтобы интерпретируя каждую из них как целое число, оно бы делилось на заданное целое $m$.
Найдите количество таких разбиений по модулю $10^9 + 7$. При определении различны ли два разбиения, рассматривайте только положение границ, а не самих цифр. То есть разбиения $2 | 22$ и $22 | 2$ являются различными.
\InputFile
Первая строка содержит два числа $n$ и $m~(1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^6)$ --- длина последовательности цифр и значение делителя. Вторая строка содержит $n$ цифр.
\OutputFile
Выведите одно число --- количество разных разбиений по модулю $10^9 + 7$.
Входные данные #1
4 2 1246
Выходные данные #1
4
Входные данные #2
4 7 2015
Выходные данные #2
0