#11 「 数数 」

统计

数学课上老师提了个问题:

「$3$ 位数中满足所包含数字不重复且为 $2$ 倍数的数有多少个?」

NanoApe 很快就算出来了。然而,她在思考着另一个更难的题目:

「在 $1$ 到 $A^n$ 中满足所包含数字不重复(用 $A$ 进制表示时)且为 $k$ 倍数的数有多少个?」

输入格式

第 $1$ 行为 $3$ 个整数 $A,n,k$ ,含义如题目所述(注意这里的 $A,n,k$ 都是用十进制表示的) 。

输出格式

输出 $1$ 行 $1$ 个整数表示答案。

样例数据

input

10 2 7

output

13

数据规模与约定

$2\leq A\leq 11,~0\leq n\leq 10^9,~1\leq k\leq 10^9$

时间限制:1s

空间限制:512MB

Author: NanoApe