시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

0 1000 10
1 1000 10
0 0 0

예제 출력 1

Case 1: 1
Case 2: 10