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