Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача G регионального тура. Числа

Автор задачи: Региональный этап Всероссийской олимпиады школьников по информатике 2008 / 2009 учебного года

Задачу добавил: alef

Успешно сдано решений: 11

Время на тест - 2 с
Максимальный объем используемой памяти - 64 Мб

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних k цифр этого числа.

Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.

Формат входных данных

Первая строка входного файла содержит три целых числа — n, C и k (1  n  50000, 1  C  108, 1 ≤ k  18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

Формат выходных данных

В выходной файл выведите последние k цифр искомого количества последовательностей без ведущих нулей.

Примеры входных и выходных данных

numbers.in

numbers.out

3 11 2

111

3

10 9 1

0123456789876543210

1

1 8 3

9

0

Примечание

Решения, работающие только для k  9, будут оцениваться из 70 баллов.


Сдать задачу

Задать вопрос жюри по этой задаче