デュードニー数

　

正の整数$x$の各桁をすべて足して得られる数の３乗が$x$になるとき、この数$x$をデュードニー数といいます。たとえば、$512$は$8$の$3$乗で、$5 + 1 + 2 = 8$となるので$512$はデュードニー数です。

この問題では、デュードニー数と似た数を考えて、その個数を求めます。

負でない整数$a$、2以上の整数$n$、および上限値$m$が与えられる。このとき、$x$の各桁をすべて足して得られる数$y$について、$x=(y+a)^n$となる$m$以下の正の整数$x$の個数を出力するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$a$ $n$ $m$

１行に、$a$ ($0 \leq a \leq 50$)、$n$ ($2 \leq n \leq 10$)と上限値$m$ ($1000 \leq m \leq 10^8$)が、すべて整数で与えられる。

出力

個数を１行に出力する。

入出力例

入力例１

16 2 1000

出力例１

2

$400 = (4+0+0+16)^2$となる数$400$、$841 = (8+4+1+16)^2$となる数$841$の２つ。

入力例２

0 3 5000

出力例２

3

$1 = 1^3$となる数$1$、$512 = (5+1+2)^3$となる数$512$、$4913 = (4+9+1+3)^3$となる数$4913$の３つ。

入力例３

2 3 100000

出力例３

0

$x$の各桁をすべて足して得られる数yについて$(y+2)^3 = x$となるような100,000以下の数$x$はない。

Note

Algorithm

 

C++

 

---