Вирішуючи завдання з інформатики, Дмитрик в черговий раз припустився помилки. Він знову вивів у вихідний файл числа, забувши розділити їх пробілами. Побачивши отриманий результат, Дмитрик спочатку засмутився, а потім задумався над наступним питанням: скільки існує різних послідовностей невід'ємних цілих чисел, таких що якщо виписати їх без прогалин, то вийде той же результат, що і в нього. Він згадав також, що його програма спромоглася вивести не довільні числа, а лише ті, що не перевершують \(C\) і не мають провідних нулів.

Щоб відповісти на поставлене питання, Дмитрик вирішив написати програму, яка дозволить йому знайти число різних послідовностей невід'ємних цілих чисел, у кожній з яких будь-яке число не перевищує \(C\). Він розумів, що таке число могло бути досить великим, тому обмежився пошуком останніх цифр цього числа.

Потрібно написати програму, яка покаже Дмитрику, як можна правильно вирішити поставлене завдання.

Формат вхідних даних

Перший рядок вхідного файлу містить три цілих числа — \(n\), \(C\) і \(k\) (\(1 ≤ n ≤ 50000\), \(1 ≤ C ≤ 10^8\), \(1 ≤ k ≤ 18\)).

У другому рядку цього файлу міститься результат роботи Дмитрикової програми, що складається з n цифр.

Формат вихідних даних

У вихідний файл виведіть останні k цифр потрібної кількості послідовностей (без провідних нулів).

Оцінювання

• Тести 1-8 — \(𝑛≤7\) Оцінюється на 30 балів.
• Тести 9-53 - додаткових обмежень немає. Група тестів оцінюється у 70 балів.

Приклад вхідних даних

3 11 2
111

Приклад вихідних даних

3

Приклад вхідних даних

19 9 1
0123456789876543210

Приклад вихідних даних

1

Приклад вхідних даних

1 8 3
9

Приклад вихідних даних

0