【问题描述】



序列a(1)，a(2)，…，a(n)以及正整数k。对于i>1，a(i)是满足下面2个性质的最小正整数：

(1) a(i) > a(i-1)；

(2) a(i) 的各位数字的和与k×a(i-1)的各位数字的和相等。

例如，a(1)=1,k=2,n=6时，该序列的前6个元素是1，2，4，8，16，23。

现给定a(1),k,n的值，计算该序列的第n项a(n)的值。



【输入形式】



输入文件为当前目录下的sequence.in。

文件只有一行，包含3个整数a(1),k,n (0<a(1)<1000 0<k,n<300000)。



【输出形式】



输出文件为当前目录下的sequence.out。

该输出文件只有一个整数，为序列的第n项a(n)，以换行符结束。

-[Descr iption of the problem sequences a (1), a (2), ..., a (n) and a positive integer k. For i>　1, a (i) satisfy the following two properties of the smallest positive integer: (1) a (i)>　a (i-1)　(2) a (i) of the digits and the k a (i-1) of the digits and the same. For example, a (1) = 1, k = 2, n = 6, the front element of the sequence 6 is 1,2,4,8,16,23. Were given a (1), k, n values ​ ​ to calculate the first term of the sequence n a (n) value. [Form] input input file is in the current directory sequence.in. File only one line containing three integers a (1), k, n (0 <a(1)<1000 0<k,n<300000)。



【输出形式】



输出文件为当前目录下的sequence.out。

该输出文件只有一个整数，为序列的第n项a(n)，以换行符结束。