IMPA/p374/p374.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>
#include <list>

using namespace std;

typedef unsigned long long nat;

int main()
{
    nat b, p, m;

    while(cin >> b >> p >> m)
    {
        // Modular exponentiation
        nat part = b % m;
        nat result = 1;
        while(p > 0)
        {
            if(p&1)
                result = (result * part) % m;

            p = p >> 1;
            part = (part*part) % m;
        }

        cout << result << endl;
    }

    return 0;
}