#include <cstdio>
using namespace std;
const int MOD=666013;
int a[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;
    }
    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;
    }
    a[0][0]=0;
    a[0][1]=a[1][0]=a[1][1]=1;
    printf("%d",lgput(n-1));

    return 0;
}