← 返回题目列表

AtCoder · atc002_b

B. n 的 p 次幂模 m

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

問題文

整数 N, M, P 被给予。

N 的 P 乘法 除以 M 后求余数。


入力

输入将以以下形式从标准输入给出。

N M P

1 行包含一个整数 打印除以 N, M, P (1≦N,M≦10^{9}, 1≦P≦10^{14}) 用空格分隔。 来自行

出力

N 的 P 乘法 除以 M 后的余数。


入力例 1

12 15 7

出力例 1

3

12 的 7 功率为 35831808 。这个 除以 15 的余数为 3 。


入力例 2

123456789 234567894 6574837563712

出力例 2

120678297

这个数字可能非常大。