题目内容

在某个进制表示中，如果一个数从最高位到最低位的位值序列，与从最低位到最高位的位值序列完全一致，则称它为回文数。例如十进制中的 1221 和 3443 都满足这一性质。

现在考虑 $r$ 进制表示。一个数的长度定义为它在 $r$ 进制下的位数，并且不允许前导零，也就是最高位不能是 0。对于固定的 $r$ 和 $n$，将所有长度为 $n$ 的 $r$ 进制回文数按十进制值从小到大排列，并从 1 开始编号。

给定进制 $r$、位数 $n$ 以及编号 $t$，请找出上述序列中第 $t$ 个回文数，输出它的十进制值。题目保证第 $t$ 个这样的回文数一定存在。

约束条件

• 进制 $r$ 为 $2$ 到 $16$ 的整数。
• 位数 $n$ 为 $1$ 到 $60$ 的整数。
• 编号 $t$ 为 $1$ 到 $9×10^8$ 的整数。
• 输出结果不超过 $10^{18}$。

输入描述

输入只有一行，按顺序给出三个整数 $r$、$n$、$t$，相邻两个整数之间用一个空格分隔。

输出描述

输出一个整数，表示第 $t$ 个长度为 $n$ 的 $r$ 进制回文数对应的十进制值。

样例1

输入

2 3 1

输出

5

说明

在 $r=2$ 时，长度为 3 的二进制回文数按从小到大排列为 $101_2$ 和 $111_2$。

第 1 个是 $101_2$，其十进制值为 $1\times2^2+0\times2^1+1\times2^0=5$。

因此输出 5。

样例2

输入

10 2 9

输出

99

说明

十进制下长度为 2 的回文数依次为 $11,22,33,\ldots,99$。

第 9 个是 $99$，它对应的十进制值就是 99。

因此输出 99。

样例3

输入

16 4 15

输出

7905

说明

在 $r=16$ 时，长度为 4 的十六进制回文数可以表示为 ABBA（其中 A 不能为 0）。

按十进制值从小到大排列，前 15 个十六进制回文数为：

$1001, 1111, 1221, 1331, 1441,$

$1551, 1661, 1771, 1881, 1991,$

$1AA1, 1BB1, 1CC1, 1DD1, 1EE1。$

因此第 $15$ 个回文数为 $1EE1$。

将其转换为十进制：

$1EE1_{16} = 1×4096 + 14×256 + 14×16 + 1= 7905$。

所以输出 $7905$。

样例4

输入

2 60 23

输出

576460776361951233