Description

Given three integers $a, b, m$, compute the value of $a^b \bmod m$.

Input Format

One line containing three integers $a, b, m$.

Output Format

A single integer representing the value of $a^b \bmod m$.

Sample 1

2 100 1007

169

Constraints & Notes

For all test cases, $1 \le a, b, m \le 10^9$.