#include <cstdio>
#define sqr(x) (x*x)
const int mod=666013;
long long f[4][4];

void putere(int n)
{   if(n>1){
    putere(n/2);
        f[2][1]=(f[2][1]*f[1][1]+f[2][2]*f[2][1])%mod;
        f[1][1]=(sqr(f[1][1])+sqr(f[1][2]))%mod;
        f[2][2]=(sqr(f[1][2])+sqr(f[2][2]))%mod;
        f[1][2]=f[2][1];
        if(n%2){
            f[1][1]=f[1][2];
            f[1][2]=f[2][2];
            f[2][2]=(f[2][1]+f[2][2])%mod;
            f[2][1]=f[1][2];}}}

int main()
{   int n;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    f[1][2]=1;
    f[2][1]=1;
    f[2][2]=1;
    putere(n+1);
    printf("%d",f[1][1]);}