题目描述

求x^p^ mod m 的值。 提示：若 p 为偶数，x ^p^ =(x ^2^ ) ^p/2^ ；若 p 为奇数，x ^p^ =x*(x ^2^ ) ^(p-1)/2^ ，该题可以采用分治法求解。

输入格式

输入三个不超过 10000 的正整数 x，p，m。

输出格式

输出x^p mod m 的值。。

样例

2 10 100

24