#include <iostream>
#include <fstream>>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int n, mat1[5][5], mat2[5][5], aux[5][5],r1,r2;

const int mod=666013;

void inmultire2()
{
    for (int i=1; i<=2; i++)
    {
        for (int j=1; j<=2; j++)
        {
            aux[i][j]=0;
        }
    }
    for (int t=1; t<=2; t++)
    {
        for (int i=1; i<=2; i++)
        {
            for (int j=1; j<=2; j++)
            {
                aux[t][i]+=(mat1[t][j]*mat2[j][i]);
                aux[t][i]=aux[t][i]%mod;
            }
        }
    }
    for (int i=1; i<=2; i++)
    {
        for (int j=1; j<=2; j++)
        {
            mat2[i][j]=aux[i][j];
        }
    }
}

void inmultire1()
{
    for (int i=1; i<=2; i++)
    {
        for (int j=1; j<=2; j++)
        {
            aux[i][j]=0;
        }
    }
    for (int t=1; t<=2; t++)
    {
        for (int i=1; i<=2; i++)
        {
            for (int j=1; j<=2; j++)
            {
                aux[t][i]+=(mat1[t][j]*mat1[j][i]);
                aux[t][i]=aux[t][i]%mod;
            }
        }
    }
    for (int i=1; i<=2; i++)
    {
        for (int j=1; j<=2; j++)
        {
            mat1[i][j]=aux[i][j];
        }
    }
}

int main()
{
    f >> n;
    n-=2;
    mat1[1][1]=1;
    mat1[1][2]=1;
    mat1[2][1]=1;
    mat1[2][2]=0;
    mat2[1][1]=1;
    mat2[1][2]=0;
    mat2[2][1]=0;
    mat2[2][2]=1;
    while (n>1)
    {
        if (n%2==0)
        {
            inmultire1();
            n/=2;
        }
        else
        {
            inmultire2();
            n--;
        }
    }
    inmultire2();
//    for (int i=1; i<=2; i++)
//    {
//        for (int j=1; j<=2; j++)
//            cout << mat2[i][j]<<' ';
//        cout << endl;
//    }
    r1=mat2[1][1]+mat2[2][1];
    r1=r1%mod;
    g << r1;
}