Возведение в степень по модулю для чисел близких к max long long

/* compute x^y mod m.
   assume m >= 2.
   overflow is impossible. */
int modpow(int x, int y, int m) {
  long acc = 1, z = x % m;
  while (y) {
    if (y & 1)
      acc = (acc * z) % m;
    z = (z * z) % m;
    y >>= 1;
  }
  return acc;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std;
 
typedef long long LL;
 
#define SPR(x) ((x)*(x))
#define len(t) ((int)t.length())
#define base 10;
#define fname ""
#define sz (1000 * 1000)
#define sz2 1000
#define EPS (1e-8)
#define INF ((int)1e9 + 9)
//const double PI  = acos(-1.0);
 
LL a , b , c , ans;
 
LL mult(LL a , LL b)
{
    LL res = 0;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            b--;
            res = (res + a) % c;
            
        }
        a = (a + a) % c;
        b /= 2;
    
    }
    return res;
    
}
 
int main(){
    //freopen(fname".in", "r", stdin);
    //freopen(fname".out", "w", stdout);
 
    cin >> a >> b >> c;
    ans = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            b--;
            ans = mult(ans , a);
        
        }
        b /= 2;
        a = mult(a , a);
    
    }
    cout << ans;
 
    return 0;
 
}