modpow.cpp

#include <iostream>

using namespace std;
typedef unsigned long long ull;

ull pow(ull p, ull n) {
  ull w = 1;
  for (ull i = 1ULL << (sizeof(ull)*8-1); i != 0; i >>= 1) {
    if ((n & i) == 0) {
      w *= w;
    } else {
      w *= w * p;
    }
  }
  return w;
}

ull modpow(ull p, ull n, ull m) {
  ull w = 1;
  for (ull i = 1ULL << (sizeof(ull)*8-1); i != 0; i >>= 1) {
    if ((n & i) == 0) {
      w *= w;
    } else {
      w *= w * p;
    }
    w %= m;
  }
  return w;
}

int main(void) {
  cout << modpow(3, 10, 1000) << endl;
  return 0;
}