题目描述

给定两个十进制非负整数 $A, B$ 和一个进制 $K$。

先把 $A$ 和 $B$ 都转换成 $K$ 进制表示，然后把 $B$ 的表示接在 $A$ 的表示后面，得到一个新的 $K$ 进制数。请输出这个新数对应的十进制值。

例如：

• $A=3$，$3$ 的二进制表示为 11；
• $B=5$，$5$ 的二进制表示为 101；
• 拼接得到 11101；
• 11101 对应的十进制值为 $29$。

输入格式

一行三个整数：

A B K

输出格式

输出一个整数，表示拼接后得到的新数的十进制值。

样例 1

3 5 2

29

样例 2

12 3 10

123

数据范围

• $0 \le A,B \le 10^9$
• $2 \le K \le 10$
• 保证答案不超过 $10^{18}$