「补档计划」十进制快速幂与 O(1) 乘

typedef long double ld;
#define long long long

inline long mul(long a, long b) {
    return (a * b - (long)((ld)a / MOD * b) * MOD + MOD) % MOD;
}

inline long modPow(long a, long b) {
    register long ret = 1;
    for (; b; b >>= 1, a = mul(a, a))
        (b & 1) ? ret = mul(a, ret) : 0;
    return ret;
}

#include <ext/numeric>

int main() {
    std::cout << __gnu_cxx::power(3, 2);
}

inline long optimizedModPow(long a, long b) {
    if (b == 0) return 1;
    for (; ~b & 1; b >>= 1, a = mul(a, a));
    register long ret = a;
    for (b >>= 1; b; b >>= 1)
        a = mul(a, a), (b & 1) ? ret = mul(a, ret) : 0;
    return ret;
}

/*
 * created by xehoth on 14-04-2017
 */
#include <bits/stdc++.h>

typedef long double ld;
#define long long long

const long MOD = 999999999999999999ll;
const int MAXN = 1000005;

inline long mul(long a, long b) {
    return (a * b - (long)((ld)a / MOD * b) * MOD + MOD) % MOD;
}

inline long modPow(long a, long b) {
    register long ret = 1;
    for (; b; b >>= 1, a = mul(a, a))
        (b & 1) ? ret = mul(a, ret) : 0;
    return ret;
}

inline long optimizedModPow(long a, long b) {
    if (b == 0) return 1;
    for (; ~b & 1; b >>= 1, a = mul(a, a));
    register long ret = a;
    for (b >>= 1; b; b >>= 1)
        a = mul(a, a), (b & 1) ? ret = mul(a, ret) : 0;
    return ret;
}

inline long quickPow(long a, char *b) {
    register long ret = 1;
    register int n = strlen(b);
    for (register int i = n - 1; i >= 0; i--)
        ret = mul(ret, optimizedModPow(a, b[i] - '0')), a = optimizedModPow(a, 10);
    return ret;
}

char b[MAXN];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    register long a;
    std::cin >> a >> b;
    std::cout << quickPow(a, b);
    return 0;
}