Cod sursă (job #185795)

#include <cstdio>

using namespace std;

int putere( int p){
    if(p==0) return 1;
    if(p==1) return 3;
    long long v=putere(p/2);
    if(p%2) return v*v%100003;
    else return 3*v*v%100003;
}
/*int putmat(int p, int &rez[3][3]){
    if(p>1){
        putmat(p/2, rez[3][3]);
        int i, j, k, cpy[3][3];
        for(i=0; i<3; i++)
                for(j=0; j<3; j++)
                    cpy[i][j]=rez[i][j];
        for(i=0; i<3; i++)
                for(j=0; j<3; j++)
                    for(k=0; k<3; k++)
                        rez[i][j]=cpy[i][k]*cpy[k][j]%100003;
        if(p%2!=0) {
            for(i=0; i<3; i++)
                for(j=0; j<3; j++)
                    for(k=0; k<3; k++)
                        rez[i][j]=cpy[i][k]*a[k][j]%100003;
        }
    }

}*/


int main()
{
    int t, n, k;
    freopen("2sah.in", "r", stdin);
    freopen("2sah.out", "w", stdout);
    scanf("%d%d%d", &t, &n, &k);
    if(t==1){
        printf("%d", putere(k-1));}
    /*else{
        int a[3][3], rez[3][3], i;
        for(i=0; i<3; i++) a[0][i]=rez[0][i]=1;
        for(i=0; i<3; i++) a[0][i]=rez[0][i]=0;
        for(i=0; i<3; i++) a[0][i]=rez[0][i]=0;
        a[1][0]=rez[1][0]=1;
        a[2][1]=rez[2][1]=1;
        //printf("%d", a[0][0]);
        putmat(n-k+1, a[3][3]);
        printf("%d", rez[0][0]);
    }*/
    return 0;
}