07/04/2025 01:14:46

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1199. Числа

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

$C$ и не имеют ведущих нулей.

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

$C$ . Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних

$k$ цифр этого числа.

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

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

Первая строка входного файла содержит три целых числа –

$n$ ,

$C$ и

$k$ (

$1 ≤ n ≤ 50\ 000$ ,

$1 ≤ C ≤ 10^8$ ,

$1 ≤ k ≤ 18$ ). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из

$n$ цифр.

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

В выходной файл выведите последние

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

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

input.txt

3 11 2
111

output.txt

input.txt

10 9 1
0123456789876543210

output.txt

input.txt

1 8 3
9

output.txt

Примечание

Решения, работающие только для

$k ≤ 9$ , будут оцениваться из 70 баллов.

Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/

29/01/2009	Областная олимпиада школьников по информатике. II тур. (7)
04/07/2018	Лето 2018 - 5 (B)
08/07/2020	Лето 2020 - 4 (B)