Істина, схована у рекурентності - Задачі

Рекурсивна функція задана наступним чином:

prb1514_1

Обчислити значення prb1514_2 , де m = 10t.

prb1514_ua

Кожний рядок містить три цілі числа: k (0 < k < 10¹⁹), n (0 < n < 10¹⁹) та t (0 < t < 10). Останній рядок містить три нулі і не опрацьовується.

Для кожного тесту в окремому рядку вивести номер тесту та значення x. Формат виведення наведено у прикладі.

Ліміт часу 1 секунда

Ліміт використання пам'яті 128 MiB

Вхідні дані #1

1234 1234 4
2323 99999999999 8
4 99999 9
888 888 8
0 0 0

Вихідні дані #1

Case #1: 736
Case #2: 39087387
Case #3: 494777344
Case #4: 91255296