← 返回题目列表

Codeforces · 17/D

D. 记事本

中文机器翻译题面 查看原题

尼克被一切非传统的事物所吸引。他不再喜欢十进制数字系统,他决定研究其他数字系统。一个以 b 为基数的数字系统引起了他的注意。在开始研究之前,他想在记事本中写下这个数字系统中所有长度为 n 且不带前导零的数字。尼克记事本中的每一页都有足够的空间准确地容纳 c 个数字。尼克只将每个合适的数字写入一次,从第一个干净的页面开始,不留任何干净的空间。尼克从来不写数字 0,因为他对零除法有不愉快的记忆。

你能帮尼克找出最后一页上会写多少个数字吗?

输入

唯一的输入行包含三个空格分隔的整数 b、n 和 c (2 ≤ b < 10106、1 ≤ n < 10106、1 ≤ c ≤ 109)。您可能会认为尼克有无限的耐心、无穷无尽的纸张和将数字表示为字符的能力。这些数字不包含前导零。

输出

在唯一的行中输出与最后一个数字在同一页上写入的数字数量。

示例

输入 #1

2 3 3

输出 #1

1

输入 #2

2 3 4

输出 #2

4

注意

在两个样本中,二进制数字系统中恰好有 4 个长度为 3 的数字。在第一个示例中,Nick 在第一页上写了 3 个数字,在第二页上写了 1 个数字。在第二个示例中,所有 4 个数字都可以写在第一页上。