题目描述

给出三个整数 $a,b,p$，请求出 $a^b \bmod p$ 的值。

输入格式

一行三个整数 $a,b,p$，相邻两个数之间用一个空格隔开。

输出格式

输出一行一个整数，表示 $a^b \bmod p$ 的结果。

输入输出样例 #1

输入 #1

2 10 1000000007

输出 #1

1024

说明

数据范围

• 对于 $100\%$ 的数据，$0\le a,b\le 10^{18}$，$1\le p\le 10^{18}$。约定 $a^0=1$。