「你信不过我？」
他挑衅地看着面前的男人，拿出一把手枪，清空子弹，只余一颗。
「看来，要想合作愉快，还得向你解释一下我的做事风格。」
他将手枪塞到对方手中，转动转轮，将枪口对准自己。
他连续扣动扳机，三声空响之后笑容无异。
「生命是一场盛大的豪赌，而我总是最后的赢家。」

砂金不光运气好，也擅长组合数学与概率论。
真理医生给了砂金一本书，书上写满了数字，从第一页开始，每一页恰好写满了 c 个数，除了最后一页可能会写不满。
书上的数满足以下条件：
1. 每个数互不相同；
2. 每个数都是一个 n 位的 b 进制数，且这些数的首位必定不是 0 ；
3. 任意一个首位不是 0 的 n 位的 b 进制数，都可以在这些数中找到；
求最后一页上有多少个数。

一行包含三个正整数 b,n,c (2≤b<10^1000000, 1≤n<10^1000000, 1≤c≤10^9) ，表示进制数、位数、每页包含的数的个数。

输出有一个整数，表示答案。

样例1：
2 3 3


样例2：
2 3 4

样例1：
1

样例2：
4

样例解释：
两个样例都是对于不包含前导零的长度为 3 的 2 进制数，符合条件的共有 4 个数：
100, 101,110,111
在样例1 中，每页写 3 个，最后一页有 1 个数；
在样例2 中，每页写 4 个，最后一页有 4 个数；