Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят \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} цифр искомого количества последовательностей без ведущих нулей.