#include<fstream>
#define M 666013
using namespace std;
ifstream f("kfib.in"); ofstream g("kfib.out");
typedef long long mat[2][2];
void prod(mat A, mat B, int n)
{   if(n==0) {B[0][0]=B[1][1]=1; B[0][1]=B[1][0]=0;}
    else
    {   mat C,D;
        prod(A,C,n/2);
        if(n%2)
        {   for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                {   D[i][j]=0;
                    for(int q=0; q<2; q++)
                        D[i][j]+=C[i][q]*C[q][j];
                    D[i][j]%=M;
                }
            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                {   B[i][j]=0;
                    for(int q=0; q<2; q++)
                        B[i][j]+=D[i][q]*A[q][j];
                    B[i][j]%=M;
                }
        }
        else
		{   for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                {   B[i][j]=0;
                    for(int q=0; q<2; q++)
                        B[i][j]+=C[i][q]*C[q][j];
                    B[i][j]%=M;
                }
	    }
    }
}
int main()
{   int k;
    f>>k;
    if(k<2) g<<k<<'\n';
    else
    {   mat A,U;
        A[0][0]=0; A[0][1]=A[1][1]=A[1][0]=1;
        prod(A,U,k-2);
        g<<(U[1][0]+U[1][1])%M;
    }
    g.close();
    f.close();
    return 0;
}