时间限制：50毫秒　　内存限制：256M

---

【问题描述】

　　输入 \(a,n,M\) 的值，求 \(a^n\ mod\ M\) 的值。

【输入格式】

　　输入 \(a,n,M\)。

【输出格式】

　　输出 \(a^n\ mod\ M\) 的值。

【输入输出样例】

　Input

2 10 9

　Output

7

【数据限制】

　　\(1 < a,n,M ≤ 10^{14}\)，\(1 < M ≤ 10^{9}\)

【来源】

　ITer