11699번 - Digit 다국어

For a positive integer $a$, let $S(a)$ be the sum of the digits in base $l$. Also let $L(a)$ be the minimum $k$ such that $S^k(a)$ is less than or equal to $l-1$. Find the minimum $a$ such that $L(a) = N$ for a given $N$, and print $a$ modulo $m$.

The input contains several test cases, followed by a line containing "0 0 0". Each test case is given by a line with three integers $N$, $m$, $l$ ($0 \leq N \leq 10^5$, $1 \leq m \leq 10^9$, $2 \leq l \leq 10^9$).

For each test case, print its case number and the minimum $a$ modulo $m$ as described above.