시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

Given 3 positive integers A, B and C, find how many positive integers less than or equal to A, when expressed in base B, have digits which sum to C.

입력

Input will consist of a series of lines, each containing three integers, A, B and C, 2 ≤ B ≤ 100, 1 ≤ A C ≤ 1,000,000,000. The numbers A, B and C are given in base 10 and are separated by one or more blanks. The input is terminated by a line containing three zeros.

출력

Output will be the number of numbers, for each input line (it must be given in base 10).

예제 입력

100 10 9
100 10 1
750000 2 2
1000000000 10 40
100000000 100 200
0 0 0

예제 출력

10
3
189
45433800
666303

힌트