本题需要知道一个基础知识，以简化计算

很明显会有 k^n mod (k-1) = 1

所以很显然，k进制数所有数位加和与其本身，在模k-1的时候是同余的

而本题是取其k进制所有位数的和，一直进行加和直至小于k为止，那么就直接用x^y mod k-1即可，但是需要注意，题目实际是模k，那么如果最后模数是0，答案则是k-1

#include<stdio.h>
typedef long long ll;
ll AmulBmodP(ll a, ll b, ll p) {
    ll ret = 0;

    while (b) {
        if (b & 1)
            ret = (ret + a) % p;

        a = (a << 1) % p;
        b >>= 1;
    }

    return ret;
}
ll ApowBmodP(ll a, ll b, ll p) {
    ll ret = 1;

    while (b) {
        if (b & 1)
            ret = AmulBmodP(ret, a, p);

        a = AmulBmodP(a, a, p);
        b >>= 1;
    }

    return ret % p;
}
ll x, y, k;
ll ans;
int main() {
    while(scanf("%lld%lld%lld", &x, &y, &k) != EOF) {
        ans = ApowBmodP(x, y, k - 1);
        if(ans == 0) ans += k - 1;
        printf("%lld\n", ans);
    }
}