← 返回题目列表

AtCoder · summerfes2018_f

F. 强大的发烧!

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

配点 : 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