|
Числа - 2
(Время: 1 сек. Память: 16 Мб Сложность: 45%)
Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.
Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних K цифр этого числа.
Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа – N, C и K (1 ≤ N ≤ 50000, 1 ≤ C ≤ 108, 1 ≤ K ≤ 18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из N цифр.
Выходные данные
В выходной файл OUTPUT.TXT выведите последние K цифр искомого количества последовательностей без ведущих нулей.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 11 2
111 | 3 |
| 2 | 19 9 1
0123456789876543210 | 1 |
| 3 | 1 8 3
9 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
