#include <stdio.h>
#include <stdlib.h>
#define MOD 666013
long long m[32][2][2];
long long a[2][2],z[2][2];
int x=0;
void prod()
{
    int i,j,k;
    for(i=0; i<=1; i++)
        for(j=0; j<=1; j++)
            for(k=0; k<=1; k++)
                z[i][j]=(z[i][j]+((a[k][j]%MOD)*(a[i][k]%MOD))%MOD)%MOD;
    for(i=0; i<=1; i++)
        for(j=0; j<=1; j++)
            a[i][j]=z[i][j],z[i][j]=0;
}
void prod2()
{
    int i,j,k,y;
    for(y=1; y<=x; y++){
        for(i=0; i<=1; i++)
            for(j=0; j<=1; j++)
                for(k=0; k<=1; k++)
                    z[i][j]=(z[i][j]+((a[i][k]%MOD)*(m[y][k][j]%MOD))%MOD)%MOD;
        for(i=0; i<=1; i++)
            for(j=0; j<=1; j++)
                a[i][j]=z[i][j],z[i][j]=0;
    }
}
void retinere()
{
    x++;
    int i,j;
    for(i=0; i<=1; i++)
        for(j=0; j<=1; j++)
            m[x][i][j]=a[i][j];
}
void lgput(k)
{
    if(k>1)
    {
        if(k%2==1)
            retinere();
        prod();
        lgput(k/2);
    }
}
int main()
{
    int k,i;
    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=1;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    lgput(k);
    prod2();
    printf("%lld\n",a[1][0]);

    return 0;
}