Розбиття цифр

Дано послідовність з $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$.

Приклади