Description
快速幂是一种快速计算底数 n 次幂的方法，实现快速幂函数 qpow(x, n) 计算 xn 的流程如下：
1、若 n==0，则返回 1；否则设 y = qpow(x, n/2)，进入下一步。
2、若 n 为偶数，则返回 y * y；否则进入下一步。
3、此时 n 为奇数，返回 x * y * y。
现给定 x、n 和 m，请参考 qpow(x, n)，实现 qpow(x, n, m) 函数计算 xn % m 的结果。
Input
多组数据。
每组输入一行，包含三个正整数 x、n 和 m。(1 ≤ x, n, m ≤ 109)
文件以EOF结束。
Output
每组输出一行，包含一个整数，为 xn % m 的结果。
10 100 1
687 123789 123
1000000000 1000000000 123124