Числа#464
Розв'язуючи задачу з інформатики, Вовчик вкотре припустився помилки: він вивів числа, забувши розділити їх пропусками. Побачивши отриманий результат, Вовчик спочатку засмутився, а потім задумався: скільки існує різних послідовностей невід'ємних цілих чисел, таких, що якщо їх записати підряд (без пропусків), то отримається та ж сама послідовність цифр, що і в нього. Він також згадав, що його програма могла виводити лише числа, не більші за і без початкових нулів.
Щоб відповісти на це питання, Вовчик вирішив написати програму, яка дозволить знайти кількість різних послідовностей невід'ємних цілих чисел, у яких кожне число не перевищує , а при їх з'єднанні підряд утворюється рівно задана послідовність з цифр. Оскільки відповідь може бути дуже великою, потрібно вивести лише останні цифр цієї кількості.
Перший рядок містить три цілих числа , і (1 \leq n \leq 50000, 1 \leq c \leq 10^8, 1 \leq k \leq 18). Другий рядок містить послідовність з цифр — результат роботи програми Вовчика.
Виведіть останні цифр шуканої кількості послідовностей (без початкових нулів ані у послідовностях, ані у відповіді).
Приклад 1