자릿수 합

시간 제한1초메모리 제한128 MB

요약
각 질의마다 A 이하의 양의 정수 중 B진법 자릿수 합이 C인 수의 개수를 구합니다.
난이도

보통10점 중 4점

유형
동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

양의 정수 AA, BB, CC가 주어진다. AA 이하의 양의 정수 가운데 BB진법으로 나타냈을 때 각 자리 숫자의 합이 CC가 되는 수는 몇 개인가?

입력

입력은 여러 줄로 이루어진다. 각 줄에는 정수 AA, BB, CC가 하나 이상의 공백으로 구분되어 주어지며, 2≤B≤1002 \le B \le 100, 1≤A,C≤1091 \le A, C \le 10^9이다. 세 수 모두 10진법으로 주어진다. 마지막 줄에는 0이 세 개 주어지고, 이 줄은 처리하지 않는다.

출력

각 입력 줄마다 조건을 만족하는 수의 개수를 10진법으로 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    100 10 9
100 10 1
750000 2 2
1000000000 10 40
100000000 100 200
0 0 0
    예상 출력
    10
3
189
45433800
666303