时空限制

1S/512M

题目描述

给定变异参数 $m$，定义对数字 $x$ 进行一次“变异”操作：将 $x$ 变为 $x$ 的每一位上的数字加起来再加 $m$ 得到的新数字。

比如当 $m=2$ 时， $315$ 进行一次变异结果为 $3+1+5+2=11$。

求对数字 $n$ 进行 $k$ 次变异操作后的结果。

格式

输入格式

第一行包含三个整数 $n,m,k$，分别初始数字、变异参数和变异操作的次数。

输出格式

输出一个整数表示对 $n$ 进行 $k$ 次变异操作后的结果。

样例

样例输入 #1

996 0 2

样例输出 #1

6

样例解释 #1

第一次变异的结果为 $24$，第二次变异的结果为 $6$。

样例输入 #2

12345 6 7

样例输出 #2

12

数据规模

对于 $40\%$ 的数据，$1\leq n\leq 10^{18}$，$1\leq k\leq 100$。

另有 $20\%$ 的数据，$m=0$。

对于 $100\%$ 的数据，$1\leq n\leq 10^{100000}$，$0\leq m\leq 10^6$，$1\leq k\leq 10^{18}$。