Цифры

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

Примеры