Słynny bajtocki specjalista z zakresu teorii gier Baj Tash 发明了一种非常有趣的游戏。该游戏的棋盘由若干个格子排成一条直线组成。起初，棋盘的每个格子上都有一个棋子。棋子有两种颜色：蓝色和红色。

玩家手中有若干个由蓝色与红色棋子组成的“模板”。玩家轮流行动。每位玩家可以从棋盘上取走一组棋子，使其排列方式与某个模板完全一致（棋子的颜色及其相对位置必须一致；但模板允许缩放和翻转）。例如，对于模板 $CNCN$ 与棋盘 $CNCCCCCNCCC$，玩家可以取走第 2、4、6、8、10 个棋子（模板被翻转并按 2 倍缩放）。接着，玩家可以拿走所有由于不匹配任何模板而在后续回合中必定无法被取走的棋子。每取走这样一个棋子就获得 1 分。最终得分更高的玩家获胜。

为了致富，Baj Tash 将他的游戏展示给了世界第二富豪——来自 Bajtycja 的 Gill Bytes。

Bytes 非常喜欢这款游戏（很大程度上是因为 Tash 很狡猾地让 Bytes 赢了几次），并问 Tash 想要怎样的报酬。Tash 表示，他希望得到的 bajtyckie cent 数量等于用于当作棋子的蓝宝石与红宝石在一条直线上排列的方案数。例如，2 颗红宝石（R）和 2 颗蓝宝石（S）可以用 6 种方式排列：RRSS、RSRS、RSSR、SRRS、SRSR、SSRR。Bytes 欣然同意。

Tash 离开后，Bytes 命令你——他雇佣的程序员——计算他需要支付多少钱。

Bajtycja 有一种有趣的货币系统：10 bajtyckie cent 等于 1 bajtycka dima，10 bajtyckich dim 等于 1 bajtycki dolar，10 bajtyckich dolarów 等于 1 bajtycki hamilton，如此类推；任意一种 bajtyckie 货币单位的 10 个，都等于下一种更大单位的 1 个。Gill Bytes 非常一丝不苟，因此他最关心的是他承诺支付的报酬中最低位的数字。他想知道：将报酬用“使其数值为整数的最大货币单位”表示时，其末尾 $k$ 位数字是什么。

输入格式

第一行包含三个整数 $r$、$s$ 和 $k$（$1 \le r, s \le 10^{15}$，$1 \le k \le 9$），分别表示红宝石数量、蓝宝石数量，以及 Bytes 需要的数字位数。

在价值 30% 分数的测试中，满足条件 $s < 9$。

在价值 30% 分数的测试中，满足条件 $k = 1$。

输出格式

输出报酬的最后 $k$ 位数字。如果报酬不足 $k$ 位，则需要在前面补前导零，使得总共恰好输出 $k$ 位。

样例数据

对于输入数据：

11 5 9

正确输出为：

000004368