#include<stdio.h>

FILE *fin,*fout;
long long int temp[3][3],mat[3][3],n,keep[3][3];

void inm()
{
    for(int i=1;i<3;i++)
    {
        for(int j=1;j<3;j++)
        {
            temp[i][j]=0;
            for(int k=1;k<3;k++)
            {
                temp[i][j]+=mat[i][k]*mat[k][j];
                temp[i][j]%=666013;
            }
        }
    }

    for(int i=1;i<3;i++)
    {
        for(int j=1;j<3;j++)
        {
            mat[i][j]=temp[i][j];
        }
    }
}

void pow(int p)
{
    if(p!=1)
    {
        pow(p/2);
        inm();
        if(p%2==1)
        {
            for(int i=1;i<3;i++)
            {
                for(int j=1;j<3;j++)
                {
                    temp[i][j]=0;
                    for(int k=1;k<3;k++)
                    {
                        temp[i][j]+=mat[i][k]*keep[k][j];
                        temp[i][j]%=666013;
                    }
                }
            }
            for(int i=1;i<3;i++)
            {
                for(int j=1;j<3;j++)
                {
                    mat[i][j]=temp[i][j];
                }
            }
        }
    }
}

int main()
{
    fin=fopen("kfib.in","r");
    fout=fopen("kfib.out","w");

    fscanf(fin,"%d",&n);

    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;

    keep[1][2]=1;
    keep[2][1]=1;
    keep[2][2]=1;

    pow(n-1);

    fprintf(fout,"%d",mat[2][2]);
}