O(sqrt(m))的欧拉定理水过去了，按理来说运算量级1e9应该是过不去的，我看之前好像有人提过，管理员也update了数据但是还是被水过了（无卡常）：

#include <cstdio>
#include <cctype>
#include <vector>

typedef unsigned long long ull;

ull fpow(ull a,ull b,ull m){
    
    ull cnt;
    
    if (b == 0) return 1 % m;
    else if (b == 1) return a % m;
    cnt = fpow(a,b / 2,m);
    cnt *= cnt,cnt %= m;
    if (b % 2 == 1) cnt *= a,cnt %= m;
    
    return cnt;
}

ull a,b,m;

ull phi(ull x){
    
    ull cnt;
    std::vector <ull> v;
    long double ans = x;
    
    for (ull i = 2;i * i <= x;i++){
        
        cnt = 0;
        while (x % i == 0) x /= i,cnt++;
        if (cnt) v.push_back(i);
        
    }
    if (x != 1) v.push_back(x);
    for (ull i = 0;i < v.size();i++) ans *= (v[i] - 1.0l) / v[i];
    
    return ans;
}

#define read(a){\
    \
    a = 0;\
    ull tmp = phi(m);\
    char ch = getchar_unlocked();\
    \
    while (!isdigit(ch)) ch = getchar_unlocked();\
    while (isdigit(ch))\
        a = (a * 10 + ch - '0') % tmp,ch = getchar_unlocked();\
    if (a == 0) a += tmp;\
    \
}

int main(){
    
    scanf("%llu%llu",&a,&m);
    read(b);
    printf("%llu\n",fpow(a,b,m));
    
    return 0;
}