问题描述

输入 $3$ 个正整数 $a,b,p$。

输出 $a^b \bmod p$ 的值。

输入格式

输入一行三个正整数，分别表示 $a,b,p$。

$(1\le a,p\le 10^9,1\le b\le 10^{18})$

输出格式

输出一行一个数字，表示 $a^b \bmod p$ 的值。

样例输入

2 10 1000

样例输出

24