题目描述

样例

对于非负整数 $x$，定义 $\operatorname{big}(x)$ 为它的十进制表示中最大的数字。例如，$\operatorname{big}(172)=7$，$\operatorname{big}(2014)=4$，$\operatorname{big}(0)=0$。

给定初始值 $A$、模数 $M$ 和天数 $N$。第 $1$ 天的数值为 $A$；从第 $2$ 天起，每天将当前数值 $x$ 更新为

求第 $N$ 天的数值。

输入格式

从标准输入读入一行三个整数 $A,M,N$。

输出格式

向标准输出输出一行一个整数，表示第 $N$ 天的数值。

数据范围

所有输入均满足：

• $1\le A<M$；
• $1\le M\le 10^{18}$；
• $1\le N\le 10^{18}$。

子任务

样例 1

2014 2015 1

2014

样例 2

14 25 115

16

样例 2 说明

数值依次为

每 $12$ 天重复一次。第 $115$ 天与第 $7$ 天相同，数值为 $16$。

样例 3

193792 211373 602033015576834098

114370

样例 4

796853790122521195 846079968484263061 588117963395639659

35027461383071256