long long power_mod(long long a, long long n, long long mod) {
    if (n == 0)
        return 1;
    a = a % mod;
    if (n == 1)
        return a;
    long long pw = power_mod(a, n / 2, mod);
    long long pw2 = pw * pw % mod;
    if (n & 2 == 0)
        return pw2;
    return pw2 * a % mod;
}