题目描述

给定 $3$ 个正整数 $n$、$b$ 和 $s$，生成以给定进制的数字 $s$ 开始的接下来 $n$ 个 $b$ 进制数字。我们确保进制介于 $2$ 和 $9$ 之间（含 $2$ 和 $9$）并且 $s$ 是一个 $b$ 进制的有效数字。请计算生成数字的各个数位上的所有数字中，在该进制下可能出现的最大数字一共出现的次数，以十进制表示。

输入格式

将会有三个整数，分别表示生成值的数量，要使用的进制（介于 $2$ 和 $9$ 之间，包含 $2$ 和 $9$），给定进制的起始值（不超过 $16$ 位）。

输出格式

对于每组 $3$ 个输入值，输出一个十进制数字，表示生成的数列中输入进制的数字各个数位上的最大数字出现的次数。

输入输出样例

输入 #1

15 8 2

输出 #1

2

输入 #2

20 3 12

输出 #2

21

输入 #3

25 5 324

输出 #3

24

输入 #4

13 9 1652

输出 #4

1

输入 #5

45 2 1111011

输出 #5

170

说明/提示

【样例解释】

样例 #1 解释： 如果 $n = 15$, $b = 8$ 且 $s = 2$，生成的数字是 $2、 3、 4、 5、 6、 7、10、11、12、13、14、15、 16、17、20$。八进制数各个数位上最大可能数是 $7$，并且出现了 $2$ 次。