005 - デュードニー数

問題文

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

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

課題

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

入力・出力

入力

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

a n m

1行に、a(0≦a≦50)、n(2≦n≦10)と上限値m(1000≦m≦10⁸)が、すべて整数で与えられる。

時間制限

入力に対して、実行時間が8秒を超えてはならない。

出力

個数を1行に出力する。

入出力例

入力例 1

16 2 1000

出力例 1

2

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

入力例 2

0 3 5000

出力例 2

3

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

入力例 3

2 3 100000

出力例 3

0

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