#include <stdio.h>
#include <stdlib.h>

#define MOD 666013

long long rez[3][3], rez_cp[3][3], a[3][3], a_cp[3][3];

int main()
{
    int k, i, j;
    FILE *fi, *fo;
    fi = fopen("kfib.in", "r");
    fo = fopen("kfib.out", "w");
    fscanf(fi, "%d", &k);

    rez[1][1]=rez[2][2]=1;
    a[1][2]=a[2][1]=a[2][2]=1;

    k-=2;
    while(k>0) {
        if(k%2==1) {
            for(i=1; i<=2; i++)
                for(j=1; j<=2; j++)
                    rez_cp[i][j]=rez[i][j];
            rez[1][1]=(rez_cp[1][1]*a[1][1] + rez_cp[1][2]*a[2][1])%MOD;
            rez[1][2]=(rez_cp[1][1]*a[1][2] + rez_cp[1][2]*a[2][2])%MOD;
            rez[2][1]=(rez_cp[2][1]*a[1][1] + rez_cp[2][2]*a[2][1])%MOD;
            rez[2][2]=(rez_cp[2][1]*a[1][2] + rez_cp[2][2]*a[2][2])%MOD;

        }
        for(i=1; i<=2; i++)
            for(j=1; j<=2; j++)
                a_cp[i][j]=a[i][j];
        a[1][1]=(a_cp[1][1]*a_cp[1][1] + a_cp[1][2]*a_cp[2][1])%MOD;
        a[1][2]=(a_cp[1][1]*a_cp[1][2] + a_cp[1][2]*a_cp[2][2])%MOD;
        a[2][1]=(a_cp[2][1]*a_cp[1][1] + a_cp[2][2]*a_cp[2][1])%MOD;
        a[2][2]=(a_cp[2][1]*a_cp[1][2] + a_cp[2][2]*a_cp[2][2])%MOD;
        k/=2;
    }

    fprintf(fo, "%d", (rez[1][2]+rez[2][2])%MOD);

    fclose(fi);
    fclose(fo);
    return 0;
}