#include <fstream>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
void zlai (int);
int z[2][2],a[2][2],b[2][2];

int main()
{
    int i=0,j,n,aux;

    a[0][0]=z[0][0]=0;
    a[0][1]=z[0][1]=1;
    a[1][0]=z[1][0]=1;
    a[1][1]=z[1][1]=1;
    fin>>n;
    zlai(n-1);
    //for (i=0;i<2;i++)
    //{
    //    for (j=0;j<2;j++)
    //        fout<<z[i][j]<<" ";
    //    fout<<"\n";
    //}
    fout<<z[1][1]%666013;

    fin.close();
    fout.close();
    return 0;
}

void zlai ( int i )
{
    //int b[2][2];

    while(i>1)
    {
        b[0][0]=a[0][0]*z[0][0]+a[0][1]*z[1][0];
        b[0][1]=a[0][0]*z[0][1]+a[0][1]*z[1][1];
        b[1][0]=a[1][0]*z[0][0]+a[1][1]*z[1][0];
        b[1][1]=a[1][0]*z[0][1]+a[1][1]*z[1][1];

        z[0][0]=b[0][0]%666013;
        z[0][1]=b[0][1]%666013;
        z[1][0]=b[1][0]%666013;
        z[1][1]=b[1][1]%666013;
        i--;
    }
}