Задачі
Цифри
Цифри
Для додатнього числа a визначимо функцію S(a), рівну сумі його цифр у системі числення з основою l. Крім того, нехай L(a) - мінімальне k, для якого S^k(a) не перевищує l-1. Потрібно знайти мінімальне a, таке що L(a)=N для заданого N і вивести його по модулю m.
Вхідні дані
N
m
l
0
≤
N
≤ 10
^5
^{ }
1
≤
m
≤
10
^9
2
≤
l
≤
10
^9
Вхідний файл містить декілька тестів і завершується рядком "0 0 0". Кожен тест задано у окремому рядку, який містить трійку чисел , , (, , ).
Вихідні дані
Для кожного тесту виведіть його номер та мінімальне значення a по модулю m.
Приклад
Вхідні дані #1
0 1000 10 1 1000 10 0 0 0
Вихідні дані #1
Case 1: 1 Case 2: 10