Description

给出三个整数 a,b,m,求（a^b） % m的值

Format

Input

三个整数a,b,m。

Output

一个整数，表示（a^b） % m的值。

Sample 1

Input

2 100 1007

Output

Limitation

1s, 32MiB for each test case.
a,b,m<=10^9

Source

难度

6

分类

快速幂、数论点击显示

标签

递交数

已通过

11

通过率

73%

上传者