#include<cstdio>
#define mod 666013

long long a[3][3],p[3][3],i,j,n,k;

void ori(long long a[][3],long long b[][3])
{
    long long  r[3][3];
    r[1][1]=((a[1][1]*b[1][1])%mod+(a[1][2]*b[2][1])%mod)%mod;
    r[1][2]=((a[1][1]*b[1][2])%mod+(a[1][2]*b[2][2])%mod)%mod;
    r[2][1]=((a[2][1]*b[1][1])%mod+(a[2][2]*b[2][1])%mod)%mod;
    r[2][2]=((a[2][1]*b[1][2])%mod+(a[2][2]*b[2][2])%mod)%mod;

    p[1][1]=r[1][1];
    p[1][2]=r[1][2];
    p[2][1]=r[2][1];
    p[2][2]=r[2][2];
}

void ridica(long long k)
{
    if(k<=1) return ;
    else if(k%2==0)
    {
        ridica(k/2);
        ori(p,p);
    }
    else
    {
        ridica((k-1)/2);
        ori(p,p);
        ori(p,a);
    }
}


int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%lld",&n);

    if(n==0)
    {
        printf("0\n");
        fclose(stdin);
        fclose(stdout);
        return 0;
    }

    a[1][1]=p[1][1]=0;
    a[1][2]=p[1][2]=1;
    a[2][1]=p[2][1]=1;
    a[2][2]=p[2][2]=1;

    ridica(n);

    printf("%lld\n",p[1][2]);

    fclose(stdin);
    fclose(stdout);

    return 0;
}