Разбиение цифр

Задана последовательность из $n$ десятичных цифр. Разбейте ее на несколько (одну или более) последовательностей рядом стоящих цифр так, чтобы интерпретируя каждую из них как целое число, оно бы делилось на заданное целое $m$.

Найдите количество таких разбиений по модулю $10^9+7$. При определении различны ли два разбиения, рассматривайте только положение границ, а не самих цифр. То есть разбиения $2|22$ и $22|2$ являются различными.

Входные данные

Первая строка содержит два числа $n$ и $m(1\le n\le 3\cdot 10^5,1\le m\le 10^6)$ — длина последовательности цифр и значение делителя. Вторая строка содержит $n$ цифр.

Выходные данные

Выведите одно число — количество разных разбиений по модулю $10^9+7$.

Примеры