Description

求 a 的 b 次方对 p 取模的值。

Format

Input

三个整数 a,b,p ,在同一行用空格隔开。\( 0≤a,b,p≤10^9 \)

Output

输出一个整数，表示a^b mod p的值。

Sample 1

Input

3 2 7

Output

2

Limitation

1s, 65536KiB for each test case.

Hint

Free Pascal Code

C++ Code

#include <iostream>
using namespace std;

int main(){
    int a,b,p;
    cin >> a >> b >> p;
    int ans = 1 % p;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a % p;
        }
        a = 1ll * a * a % p;
    }
    cout << ans;
}