Digit Sums -- Problem U (150 points)

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 be from the file PROBLEMU.DAT and will consist of a series of lines, each containing the numbers A, B and C. 0 < A <= 1,000,000,000, B <= 100, 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).

Example Input

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

Example Output