Cod sursă (job #189543)

#include <cstdio>
#define MOD 100003

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==0) return (v*v)%100003;
    else return (3*v*v)%100003;
}
void putmat(int a[3][3], int p, int rez[3][3]){ int i, j, k, cpy[3][3];
    if(p==1){
        for(j=0; j<3; j++)
            for(i=0; i<3; i++)
                rez[j][i]=a[j][i];
    }
    else if(p%2==0){
        putmat(a, p/2, cpy);
        for(i=0; i<3; i++)
        for(j=0; j<3; j++)
        {
            rez[i][j]=0;
            for(k=0; k<3; k++)
                rez[i][j]=(rez[i][j]+(long long)cpy[i][k]*(long long)cpy[k][j]%MOD);
            rez[i][j]%=MOD;
        }
    }
        else{
            putmat(a, p-1, cpy);
            for(i=0; i<3; i++)
        for(j=0; j<3; j++)
        {
            rez[i][j]=0;
            for(k=0; k<3; k++)
                rez[i][j]=(rez[i][j]+(long long)a[i][k]*(long long)cpy[k][j]%MOD);
            rez[i][j]%=MOD;
        }
        }



}


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]=1;
        for(i=0; i<3; i++) a[1][i]=0;
        for(i=0; i<3; i++) a[2][i]=0;
        a[1][0]=rez[1][0]=1;
        a[2][1]=rez[2][1]=1;

        putmat(a,n-k+1, rez);
        printf("%d", rez[0][0]);
    }
    return 0;
}