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