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