Цифри

Для додатнього числа 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.

Приклади