#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIFQ9X19pbnQxMjhfdDtUIG09MWUxMSszO1QgZihUIGEsVCByPTEsVCBuPW0tMil7cmV0dXJuIG4/ZihhKmEtYSphL20qbSxuJjE/ciphLXIqYS9tKm06cixuLzIpOnI7fQoKaW50IG1haW4oKXsKICBjb3V0IDw8IGludDY0X3QoZigyKSkgPDwgZW5kbDsKICBjb3V0IDw8IGludDY0X3QoZigzKSkgPDwgZW5kbDsKICBjb3V0IDw8IGludDY0X3QoZig1MDAwMDAwMDAwMikpIDw8IGVuZGw7CiAgY291dCA8PCBpbnQ2NF90KGYoMTAwMDAwMCkpIDw8IGVuZGw7Cn0K