Цифри#3563

Цифри

2 секунди

64 мегабайти

Легка

Для додатного числа $a$ визначимо функцію $S (a)$ , що дорівнює сумі його цифр у системі числення з основою $l$ . Крім того, нехай $L (a)$ — мінімальне $k$ , для якого $S^{k} (a)$ S^k(a) не перевищує $l - 1$ l - 1. Потрібно знайти мінімальне $a$ , таке що $L (a) = N$ L(a) = N для заданого $N$ і вивести його по модулю $m$ .

Вхідні дані

Вхідний файл містить декілька тестів і завершується рядком 0 0 0. Кожен тест задано у окремому рядку, який містить три числа $N$ , $m$ , $l$ ( $0 \leq N \leq 1 0^{5}$ 0 \leq N \leq 10^5, $1 \leq m \leq 1 0^{9}$ 1 \leq m \leq 10^9, $2 \leq l \leq 1 0^{9}$ 2 \leq l \leq 10^9).

Вихідні дані

Для кожного тесту виведіть його номер та мінімальне значення $a$ по модулю $m$ .

Приклади

Приклад

1 5 10
2 1000 17
0 0 0

1 1
2 10

Приклад 1