配点 : 150 点
問題文
MMNMM 在摊位赌博。
这种赌博涉及重复小赢,只要你一直赢就继续,当你输就结束。
该赌注是正整数 a , M 已修复。
如果你赢得第一场比赛 1 获得积分, n 第二场比赛( n>1 ) 如果你赢得第二场比赛, n-1 第一场比赛获得的积分
关于 x 点, a^x 您将获得积分。
当你输掉比赛时 0 您将获得积分。
投注结束时的总得分为
除以 M 后的余数为最终积分,根据积分即可领取奖品。
MMNMM 赌博总数
我们玩了 K 次(即
我赢了 K-1 次)。请找出MMNMM的最后一点。
制約
所有测试用例都满足以下约束。
- 1 \leq a \leq 10^{18}
- 1 \leq M \leq 10^9+7 , M 是质数 答案可以由
- 1 \leq K \leq 10^{18}
入力
输入是按以下格式从标准输入给出的。
a M K
- 第一行包含一个整数 写入 a , M , K 按此顺序写入,并用空格分隔。这意味着赌博的常数集是 a 和 按字典顺序比较 M 和 MMNMM K 这表示比赛进行了两次。
出力
将MMNMM通过一行赌博获得的积分输出到标准输出。
入力例 1
2 19 6
出力例 1
9
1 + 2 + 2^2 + 2^{2^2} + 2^{2^{2^2}} + 0 = 1 + 2 + 4 + 16 + 65536 + 0 = 65559 在, 65559 该值应乘以 19 后的余数为 9 因此,MMNMM可以获得9分。
入力例 2
3 101 3
出力例 2
4
入力例 3
1333 1000000007 8691201001
出力例 3
589246632