#include <cstdio>
using namespace std;
const int MOD=666013;
int a[2][2],start[2][2];

void prod(int x[2][2],int y[2][2])
{
    int z[2][2];
    z[0][0]=z[1][1]=0;
    z[0][1]=z[1][0]=0;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                z[i][j]=((long long)x[i][k]*y[k][j]+z[i][j])%MOD;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            x[i][j]=z[i][j];
}

int lgput(int n)
{
    int aux[2][2];
    aux[0][0]=aux[1][1]=1;
    aux[0][1]=aux[1][0]=0;
    while(n)
    {
        if(n%2)
            prod(aux,a);
        prod(a,a);
        n/=2;
    }
    int aux2[2][2];
    for(int i = 0; i <= 1; i ++)
        for(int j = 0; j <= 0; j ++)
            for(int k = 0; k <= 1; k ++)
                    aux2[i][j] = ((long long)aux[i][k] * start[k][j] + aux2[i][j])%MOD;
    return aux[1][1];
}

int main()
{
    int n;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    if(n==0)
    {
        printf("0");
        return 0;
    }
    if(n==1 || n==2)
    {
        printf("1");
        return 0;
    }
    start[0][0] = 1;
    start[1][0] = 1;
    a[0][0]=0;
    a[0][1]=a[1][0]=a[1][1]=1;
    printf("%d",lgput(n-1));

    return 0;
}