进制下的快速幂运算与取模

题目描述

在狂狼村，有计算模运算的需求，且涉及不同进制。胖头鱼提到的《快速幂运算》技巧可用于解决此问题。

1. 幂运算定义：$n$个$a$相乘的运算称为幂运算，记作$a^n$，$a$被称为底数。幂运算具有性质$a^m \times a^n = a^{m + n}$，当$n = m$时有$a^m \times a^n = a^{2m}$，可据此快速计算一些幂的值。例如，计算$a^n$（$n$较大时），可将$n$分解为多个上述幂的乘积，从而快速算出。如计算$5^{15}$（十进制下），$5^2 = 25$，$5^4 = (5^2)^2 = 625$，$5^8 = (5^4)^2 = 390625$，$5^{15} = 5^8 \times 5^4 \times 5^2 \times 5^1 = 390625 \times 625 \times 25 \times 5$（十进制计算）。
2. 本题任务：不同物种使用不同进制进行运算，需根据给定的进制$k$，计算$a^n$模$m$的结果，答案也用$k$进制表示。$a$本身始终用十进制表示，题面中未特别注明时，其他数也用十进制表示，但计算过程需考虑进制转换。

输入格式

1. 第一行包含一个整数$k$（$2\leq k\leq10$），表示之后输入与输出的进制，用十进制表示。
2. 第二行包含两个整数$a$和$m$（$1\leq a,m$，$a,m$的位数不超过$1000$），分别表示底数和模数，用$k$进制表示。
3. 第三行包含一个整数$n$（$n$为非负整数且位数不超过$100000$），表示幂的次数，用$k$进制表示。

输出格式

输出一个整数，表示$a^n$模$m$后的结果，用$k$进制表示。

样例

样例输入1

10
5 9999
15

样例输出1

188

样例解释1

$5^{15}$（十进制）$\% 9999$（十进制）$= 30517578125$（十进制）$\% 9999$（十进制）$= 188$（十进制），答案以十进制形式给出，因为输入的进制$k = 10$。

样例输入2

2
1001 1111111111111111
110

样例输出2

1101111111001

样例解释2

运算中的数用二进制表示。$a = 1001$（二进制）$= 9$（十进制），$m = 1111111111111111$（二进制）$= 65535$（十进制），$n = 110$（二进制）$= 6$（十进制）。$9^6$（十进制）$\% 65535$（十进制）$= 531441$（十进制）$\% 65535$（十进制）$= 7176$（十进制）$= 1101111111001$（二进制），答案以二进制形式给出，因为输入的进制$k = 2$。

数据范围与提示

1. 对于所有测试点，$2\leq k\leq10$、$1\leq a,m$、$n$为非负整数且位数不超过$100000$。
2. 部分测试点特殊属性：
   • 测试点$1 - 6$：$k = 10$、$1\leq a,m\leq10000$、$n\lt1000$，表示所有数均以十进制形式给出，且都比较小。
   • 测试点$7 - 12$：$k = 2$，表示$a$、$m$、$n$都是二进制数，输出同理。
   • 测试点$13 - 16$：$n$的位数不超过$1000$。