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