Задана последовательность из n десятичных цифр. Разбейте ее на несколько (одну или более) последовательностей рядом стоящих цифр так, чтобы интерпретируя каждую из них как целое число, оно бы делилось на заданное целое m.
Найдите количество таких разбиений по модулю 109+7. При определении различны ли два разбиения, рассматривайте только положение границ, а не самих цифр. То есть разбиения 2∣22 и 22∣2 являются различными.
Первая строка содержит два числа n и m (1≤n≤3⋅105,1≤m≤106) — длина последовательности цифр и значение делителя. Вторая строка содержит n цифр.
Выведите одно число — количество разных разбиений по модулю 109+7.