Составить число, все префиксы которого кратны k

Задача Прибыльный стартап

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

Формат ввода

В единственной строке входных данных через пробел записаны три числа: n , k , d — изначальная прибыль, количество учредителей компании и количество дней, которое вы собираетесь следить за прибылью ( 1 ≤ n , k ≤ 1 0^ 9 , 1 ≤ d ≤ 1 0^ 5 ) . НЕ гарантируется, что n делится на k .

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

Выведите одно целое число x — прибыль компании через d дней. Первые цифры числа x должны совпадать с числом n . Все префиксы числа x , которые длиннее числа n на 1 , 2 , … , d цифр, должны делиться на k . Если возможных ответов несколько, выведите любой из них. Если ответа не существует, выведите − 1 . .

Пример 1

Ввод

21 108 1

Вывод

216

Пример 2

Ввод

5 12 4

Вывод

-1

Примечания

В первом тестовом примере всего один день нужно следить за прибылью. Можно дописать цифру 6 в конец числа 21 и получить прибыль, делящуюся на 108 . Во втором тестовом примере мы в первый же день не можем получить прибыль, делящуюся на k , какая бы цифра не была дописана у числу n , поэтому ответа не существует.

Не дает пройти на последнем тесте, не понимаю почему (код конечно у меня отстой, ну да ладно)

n,k,d = map(int, input().split())
s = True
for i in range(10):
    nu = n*10 + i
    if nu % k == 0:
        print(nu*10**(d-1))
        s = False
        break
if s:
    print(-1)