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.

0 1000 10 1 1000 10 0 0 0

Case 1: 1 Case 2: 10

Source: ACM-ICPC Japan Alumni Group Spring Contest 2012
, Tokyo, Japan, 2012-04-15

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/