//Ilie Dumitru
#include<cstdio>
#define mod 666013

long long int curent[2][2]={0, 1, 1, 1}, aux[2][2];

void specPrint()
{
    for(int i=0;i<4;++i) {printf("%lld ", curent[i>>1][i&1]); if(i&1) printf("\n");};
}

void calc(int K)
{
    if(K>1)
    {
        calc(K>>1);
        aux[0][0]=(curent[0][0]*curent[0][0]+curent[0][1]*curent[1][0])%mod;
        aux[0][1]=(curent[0][0]*curent[0][1]+curent[0][1]*curent[1][1])%mod;
        aux[1][0]=(curent[1][0]*curent[0][0]+curent[1][1]*curent[1][0])%mod;
        aux[1][1]=(curent[1][0]*curent[0][1]+curent[1][1]*curent[1][1])%mod;
        for(int i=0;i<4;++i) curent[i>>1][i&1]=aux[i>>1][i&1];
        if(K&1)
        {
            aux[0][0]=curent[0][1];
            aux[0][1]=(curent[0][0]+curent[0][1])%mod;
            aux[1][0]=curent[1][1];
            aux[1][1]=(curent[1][0]+curent[1][1])%mod;
            for(int i=0;i<4;++i) curent[i>>1][i&1]=aux[i>>1][i&1];
        }
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int K;
    scanf("%d", &K);
    fclose(stdin);
    if(!K)
        printf("0");
    else if(K==1)
        printf("1");
    else
    {
        calc(K);
        printf("%lld", curent[0][1]);
    }
    fclose(stdout);
    return 0;
}