AT_atc002_b.n^p mod m

给定整数 $N,M,P$。

求 $N^P$ 除以 $M$ 的余数。

第一行包含三个整数 $N,M,P$，以空格分隔。

一行，为 $N^P$ 除以 $M$ 的余数。

对于 $100\%$ 的数据，$1 \le N,M \le 10^9,1 \le P \le 10^{14}$。

说明

样例说明 1

$ 12 $ 的 $ 7 $ 次方等于 $ 35831808 $，除以 $ 15 $ 的余数为 $ 3 $。

样例说明 2

有时数字会非常的大。