#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=1E7+2;

//ll fastPower(ll base, ll power) {
//    ll ans=1;
//    while(power>0) {
//        if(power%2==1) {
            printf("奇");
//            ans*=base;
//            power--;
            printf("base = %lld\n",base);
            printf("ans = %lld, power = %lld\n",ans, power);
//        }else {
            printf("偶");
//            power/=2;
//            base*=base;
            printf("base = %lld\n",base);
            printf("ans = %lld, power = %lld\n",ans, power);
//        }
//    }
//    return ans;
//}

ll fastPower(ll base, ll power) {
    ll ans=1;
    while(power>0) {
        if(power&1) {
            ans=ans*base%mod;
        }
        power>>=1;
        base=base%mod*base%mod;
    }
    return ans;
}

int main() {
    ll a=fastPower(2,10);
    printf("%d\n",a);
    return 0;
}