// Contoh Bab 14: pangkat modulo cepat, O(log b).
//
// Compile:  g++ -std=c++17 -O2 -o pangkatmod exercises/14/02-pangkat-mod.cpp
// Jalankan: ./pangkatmod
// Contoh masukan: 3 5 1000

#include <iostream>
using namespace std;

long long pangkat_mod(long long a, long long b, long long m) {
    long long hasil = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) hasil = hasil * a % m;
        a = a * a % m;
        b /= 2;
    }
    return hasil;
}

long long pangkat_lambat(long long a, long long b, long long m) {
    long long hasil = 1;
    for (long long i = 0; i < b; i++) hasil = hasil * a % m;
    return hasil;
}

int main() {
    long long a, b, m;
    cin >> a >> b >> m;

    cout << "cepat : " << pangkat_mod(a, b, m) << "\n";
    if (b <= 10000000) cout << "lambat: " << pangkat_lambat(a, b, m) << "\n";

    // Pangkat raksasa: hanya versi cepat yang sanggup.
    cout << "2^1000000000000000000 mod 1000000007 = "
         << pangkat_mod(2, 1000000000000000000LL, 1000000007) << "\n";
    return 0;
}