#include <iostream>

using namespace std;

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

int main(){
  cout << int64_t(f(2)) << endl;
  cout << int64_t(f(3)) << endl;
  cout << int64_t(f(50000000002)) << endl;
  cout << int64_t(f(1000000)) << endl;
}