자릿수 합 반복 횟수

주어진 N, m, 진법 l마다 자릿수 합을 N번 반복해야 l보다 작아지는 가장 작은 양의 정수를 구해 m으로 나눈 나머지를 출력합니다.

어려움8정수론수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

문제

양의 정수 $a$ 에 대해, $a$ 를 $l$ 진법으로 적었을 때 각 자리 숫자의 합을 $S(a)$ 라고 하자. 또 $S^k(a) \leq l-1$ 을 만족하는 가장 작은 $k$ 를 $L(a)$ 라고 하자. 여기서 $S^0(a) = a$ 이고, $k \geq 1$ 에 대해 $S^k(a) = S(S^{k-1}(a))$ 이다.

$N$ 이 주어지면 $L(a) = N$ 인 가장 작은 양의 정수 $a$ 를 구하고, 그 값을 $m$ 으로 나눈 나머지를 출력한다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 정수 $N$ , $m$ , $l$ 이 공백으로 구분되어 한 줄에 주어진다 ( $0 \leq N \leq 10^5$ , $1 \leq m \leq 10^9$ , $2 \leq l \leq 10^9$ ).

마지막 줄에는 0 0 0이 주어진다. 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 조건을 만족하는 가장 작은 $a$ 를 $m$ 으로 나눈 나머지이다.