测试数据来自 system/1074

作业已超过截止时间，您无法递交本题目。

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

---

【问题描述】

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

【输入格式】

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

【输出格式】

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

【输入输出样例1】

　Input

2 10 9

　Output

7

【数据限制】

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

【来源】

　ITer