Задача C. Сплошные числа ≡

Условие

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

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

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

Примечание

Формат входного файла

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

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 50000

1 ≤ C ≤ 10⁸

1 ≤ k ≤ 18

Примеры тестов

3 11 2
111

3

19 9 1
0123456789876543210

1

1 8 3
9

0