Digit#3563

Digit

2 seconds

64 megabytes

Easy

For a positive integer $a$ , define the function $S (a)$ as the sum of its digits in base $l$ . Also, let $L (a)$ be the smallest $k$ such that $S^{k} (a)$ S^k(a) does not exceed $l - 1$ l-1, where $S^{k} (a)$ S^k(a) means applying the function $S$ to $a$ $k$ times.

Given $N$ , find the smallest positive integer $a$ such that $L (a) = N$ L(a) = N and output its value modulo $m$ .

Input

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

Output

For each test case, output its case number and the minimal $a$ modulo $m$ .

Examples

Example

1 5 10
2 1000 17
0 0 0

1 1
2 10

Example 1