Для положительного числа \textbf{a} определим функцию \textbf{S(a)}, равную сумме его цифр в системе счисления с основанием \textbf{l}. Кроме того, пусть \textbf{L(a)} - минимальное \textbf{k}, для которого \textbf{S^k(a)} не превышает \textbf{l-1}. Требуется найти минимальное \textbf{a}, такое что \textbf{L(a)=N} для заданного \textbf{N} и вывести его по модулю \textbf{m}. \InputFile \textbf{N} \textbf{m} \textbf{l} \textbf{0} ≤ \textbf{N} ≤ \textbf{10} \textbf{^5} ^\{ \} \textbf{1} ≤ \textbf{m} ≤ \textbf{10} \textbf{^9} \textbf{2} ≤ \textbf{l} ≤ \textbf{10} \textbf{^9} Входной файл содержит несколько тестов и завершается строкой "\textbf{0 0 0}". Каждый тест задается в отдельной строке, содержащей тройку чисел , , (, , ). \OutputFile Для каждого теста выведите его номер и минимальное значение \textbf{a} по модулю m.