题目描述

在 $Z$ 山上有一群猴子。猴子们虽然有长老主持日常事务，但没有一个大王中就不行。这天，长老们把山中的 $N$ 只猴子集中到了一起，决定选出一个大王。长老们商量了一下，为了公平起见，他们选出了两个数 $a$ 和 $b$ 并计算 $c = a^b$ ，然后从编号 $1$ 的猴子开始数，数到编号 $N$ 的之后又从编号 $1$ 的开始数，直到数到第 $c$ 个，便推举这个的猴子做大王。比如说有 $4$ 个猴子，当 $c$ 为 $2$ 时就选到 $2$ 号猴子，当 $c$ 为 $5$ 时就选到 $1$ 号猴子，当 $c$ 为 $23$ 时就选到 $3$ 号猴子等。

由于 $c$ 可能非常大，所以长老们想让你来帮忙找到这个大王。

输入格式

一行又三个数 $N,a,b$，为参选猴子的个数和长老推出的两个数。

输出格式

一个数，表示数到第 $a^b$ 是的猴子编号，即选出的大王编号。

100 3 5

43

100 1234 654321

84

数据规模

对于 $30\%$ 的数据，$1\le a\le 100,1\le b\le 100$。

对于 $100\%$ 的数据，$1\le a\le 10^4,1\le b\le 2\times 10^9, 1\le N\le 10000$。