题目描述

给定一个整数 $x$、一个非负整数 $n$，以及一个正整数 $m$，请你计算：

$x^n \bmod m$

由于 $n$ 的取值可能非常大，要求使用**倍增法（快速幂）**实现计算，使算法时间复杂度达到 $O(\log n)$。

请你实现一个函数 power(x, n, m) 完成上述运算，并在主函数中调用该函数进行测试。

输入格式

输入包含三个整数：

• $x$，满足 $-10^9 \le x \le 10^9$
• $n$，满足 $0 \le n \le 10^9$
• $m$，满足 $1 \le m \le 10^9$

输出格式

输出一个整数，即：

$(x^n) \bmod m$

输入样例

2 10 1000

输出样例

24

（因为 $2^{10} = 1024$，$1024 \bmod 1000 = 24$）