UVA1230 MODEX

许多著名的加密操作都需要模幂运算。也就是说，给定整数 $x$、$y$ 和 $n$，计算 $x ^ y \bmod n$。在这个问题中，你的任务是编写一个高效的程序来执行此计算。

输入由一行包含数据集数量 $c$，接着是 $c$ 个数据集，最后由一行包含数字 $\tt 0$ 结束。 每个数据集由一行组成，包含三个用空格分隔的正整数 $x$、$y$ 和 $n$。你可以假设 $1 < x, n < 2 ^ {15} = 32768$，且 $0 < y < 2 ^ {31} = 2147483648$。

输出由每个数据集的一行组成。第 $i$ 行包含一个正整数 $z$，使得 $$z = x ^ y \bmod n$$ 对于第 $i$ 个输入数据集给出的数字 $x$、$y$ 和 $n$。 ### 输入输出样例 #### 输入 #1 ```plain 2 2 3 5 2 2147483647 13 0 ``` #### 输出 #1 ```plain 3 11 ``` --- Translated by User 735713.