Решая задачу по информатике, Вова в очередной раз
допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их
пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался
над следующим вопросом: сколько существует различных последовательностей
неотрицательных целых чисел, таких что, если выписать их без пробелов, то
получится тот же результат, что и у него. Он вспомнил также, что его программа смогла
вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.
Чтобы ответить на поставленный вопрос, Вова решил написать
программу, которая позволит ему найти число различных последовательностей
неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно
большим, поэтому ограничился поиском только последних k цифр этого числа.
Требуется написать программу, которая покажет
Вове, как можно правильно решить поставленную им задачу.
Формат входных данных
Первая строка входного файла содержит три целых числа
— n, C и k (1 ≤ n ≤ 50000, 1 ≤ C ≤ 108,
1 ≤ k ≤ 18). Во второй строке этого файла содержится результат работы
Вовиной программы, состоящий из n цифр.
Формат выходных данных
В выходной файл выведите последние k цифр искомого количества
последовательностей без ведущих нулей.
Примеры
входных и выходных данных
|
Входные данные
|
Выходные данные
|
|
3 11 2
111
|
3
|
|
10 9 1
0123456789876543210
|
1
|
|
1 8 3
9
|
0
|
Примечание
Решения, работающие только для k ≤ 9, будут
оцениваться из 70 баллов.
