Областная олимпиада школьников по информатике

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

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

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

Первая строка входного файла содержит три целых числа – `n`, `C` и `k` (`1 ≤ n ≤ 50\ 000`, `1 ≤ C ≤ 10^8`, `1 ≤ k ≤ 18`). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из `n` цифр.

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

3 11 2
111

3

10 9 1
0123456789876543210

1

1 8 3
9

0

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