Description

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

Input

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

Output

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

Limitations

\( 0 \le a,b,p \le 10^9\)

数据保证 \(p \not = 0\)

Samples

Sample #1

Input

3 2 7

Output

2

Source

算法竞赛进阶指南