给定三个正整数，，求，其中
快速幂的时间复杂度为，最大为，；先不说可不可能超时的问题，这个数字得用字符串存储，所以快速幂并不能直接解决。
正确的解法是使用扩展欧几里得定理

欧几里得定理：
如果整数与整数互质，则有，其中是欧拉函数，表示到与互质的数的个数

如果为质数，那么，则有，此时欧拉定理就退化为费马小定理，所以费马小定理是欧拉定理的一个特殊情况。
欧拉定理的最大作用是用来"降幂"，将指数通过欧拉函数缩小，从而简化大指数幂的计算：
对于，若，则可将指数对取模，即
但是欧拉函数有两个明显的限制：
  1. 必须满足整数与整数互质
  2. 不能处理大指数且整数与整数不互质的情况
那么扩展欧几里得定理出现了！
对于任意的整数，与整数以及非负整数，有：

  1. 如果，则
  2. 如果，则
额外加上是为了避免时出现的错误

总代码：
注意的使用 
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


int ooula(int m){
    int ans = m;
    for(int i = 2; i * i <= m; i ++){
        if(m % i == 0){
            ans = ans / i * (i - 1);
            while(m % i == 0) m /= i;
        }
    }
    if(m > 1) ans = ans / m * (m - 1);
    return ans;
}

int work(string s, int oula){
    int sum = 0;
    bool ok = false;
    for(char sh : s){
        sum = sum * 10 + (sh - '0');
        if(sum >= oula){
            sum %= oula;
            ok = true;
        }
    }
    if(ok) sum += oula;
    return sum;
}

int ksm(int a, int b, int mod){
    a %= mod;
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return sum;
}

signed main(){
    HelloWorld;
    
    int a, m;
    string s;
    cin >> a >> m >> s;
    int oula = ooula(m);    
    int b = work(s, oula);
    cout << ksm(a, b, m) << endl;
    return 0;
}