Description

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

Input

三个整数 a,b,p,在同一行用空格隔开。

0≤a,b≤109

1≤p≤109

Output

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

Samples

3 2 7

2

Limitation

1s, 1024KiB for each test case.