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