#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, mat C)
{   for(int i=0;i<2;i++) for(int j=0;j<2;j++)
    {   C[i][j]=0;
        for(int q=0;q<2;q++) C[i][j]+=A[i][q]*B[q][j];
        C[i][j]%=M;
    }
}
void lgput(mat A, mat B, int n)
{   if(n==0) {B[0][0]=B[1][1]=1; B[0][1]=B[1][0]=0; return;}
    mat C;
    lgput(A,C,n/2);
    if(n&1)
    {   mat D;
        prod(C,C,D); prod(D,A,B);
    }
    else prod(C,C,B);
}
int main()
{   int k;
    f>>k;
    f.close();
    if(k<2) {g<<k<<'\n'; g.close(); return 0;}
    mat U,A={0,1,1,1};
    lgput(A,U,k-1);
    g<<U[1][1]; g.close(); return 0;
}