21681번 - Числа 다국어

문제

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

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

입력

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

출력

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

제한

힌트