Розбиття цифр#7775
Дано послідовність з десяткових цифр. Розбийте її на одну або більше прилеглих підпослідовностей так, щоб кожна підпослідовність, коли її інтерпретувати як десяткове число, ділилася на задане ціле число .
Знайдіть кількість різних таких розбиттів за модулем 10^9 + 7. При визначенні різних розбиттів ми розглядаємо лише положення меж підпослідовностей, а не самі цифри, наприклад, розбиття та вважаються різними.
У першому рядку містяться два цілі числа і m~(1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^6) — довжина послідовності та дільник відповідно. Другий рядок містить рядок, який складається з рівно цифр.
Виведіть одне ціле число — кількість різних розбиттів за модулем 10^9 + 7.
Приклад 1
Приклад 2