J3 例题-8 A的B次方

题目描述

给出三个整数 $a,b,m$，求 $a^b ~ mod ~ m$ 的值。

输入格式

一行三个整数 $a,b,m$ 。

输出格式

一个整数，表示 $a^b ~ mod ~ m$ 的值。

样例输入

2 100 1007

样例输出

169

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1\le a \le b \le m\le 10^9$。