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