#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

long long n,i;
int m[3][3],sol[3][3],aux[3][3];
void inmult (int a[3][3], int b[3][3], int c[3][3])
{
       int i,j,k;
       for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
          for(k=1;k<=2;k++)
          c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%666013;
}
int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    fin>>n;
    n--;
    m[1][1]=0;m[1][2]=1;m[2][1]=1;m[2][2]=1;
    sol[1][1]=1;sol[1][2]=0;sol[2][1]=0;sol[2][2]=1;
    for(i=0;(1<<i)<=n;i++)
    {
        if(((1<<i)& n)>0)
        {
            memset(aux,0,sizeof(aux));
            inmult(m,sol,aux);
            memcpy(sol,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        inmult(m,m,aux);
        memcpy(m,aux,sizeof(aux));
    }
    fout<<(sol[1][1]+sol[1][2])%666013;
    return 0;
}