You are given three positive integers \(a\), \(b\), and \(m\). Output the remainder of \(a^b\) modulo \(m\).

Input

The input contains three integers \(a\), \(b\), and \(m\) (\(1 \le a, b, m \le 2 \times 10^8\)).

Output

Output a single integer representing the answer.

Sample Input 1

2 200000000 199999997

Sample Output 1

103696991