#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; return;}
    mat C;
    prod(A,C,n/2);
    if(n%2)
    {   mat D;
        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;
    f.close();
    if(k<2) {g<<k<<'\n'; g.close(); return 0;}
    mat U,A={0,1,1,1};
    prod(A,U,k-1);
    g<<U[1][1]%M; g.close(); return 0;
}