PROBLEM DESCRIPTION

Given $3$ positive integers, $n$, $b$, and $s$, generate the next $n$ numbers in base $b$ starting with $s$ in the given base. We guarantee that the base will be between $2$ and $9$ inclusive. We guarantee that $s$ is a valid number in base $b$. Find the base $10$ value for the number of times the largest possible digit in the given base is found among all of the digits in the numbers generated.

INPUT FORMAT

There will be three integers representing the number of values to be found, the base to be used between $2$ and $9$ inclusive, and the starting value in the base given that will be no more than $16$ digits.

OUTPUT FORMAT

For each set of $3$ input values, output a base $10$ number representing the number of times the largest digit in the inputted base occurs in the sequence of numbers generated.

SAMPLE

INPUT #1

15 8 2

OUTPUT #1

2

INPUT #2

20 3 12

OUTPUT #2

21

INPUT #3

25 5 324

OUTPUT #3

24

INPUT #4

13 9 1652

OUTPUT #4

1

INPUT #5

45 2 1111011

OUTPUT #5

170

EXPLANATION

Sample #1 Explanation

If $n=15$, $b=8$, and $s=2$, the numbers generated are $2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20$. The largest possible digit in base $8$ is $7$ which occurs $2$ times.