#include <iostream>
#include <fstream>
#define prim 666013
using namespace std;

ifstream fi("kfib.in");
ofstream fo("kfib.out");
struct matrix
{
    long long a11,a12,a21,a22;
};

matrix operator *(matrix x, matrix y)
{
    matrix rezultat;

    rezultat.a11=(x.a11*y.a11%prim+x.a12*y.a21%prim)%prim;
    rezultat.a12=(x.a11*y.a12%prim+x.a12*y.a22%prim)%prim;
    rezultat.a21=(x.a21*y.a11%prim+x.a22*y.a21%prim)%prim;
    rezultat.a22=(x.a21*y.a21%prim+x.a22*y.a22%prim)%prim;


    return rezultat;
}

matrix ridicareLog(matrix baza,long long putere)
{
        matrix raspuns;
        raspuns.a11=1;
        raspuns.a12=0;
        raspuns.a21=0;
        raspuns.a22=1;

    for(long long i=1; i<(1<<30); i=i*2)
    {
        if(putere&i)
        {
            raspuns=raspuns*baza;
        }

        baza=baza*baza;

    }

    return raspuns;
}


void print(matrix x)
{
    cout<<x.a11<<" "<<x.a12<<endl;
    cout<<x.a21<<" "<<x.a22<<endl;
}

int main()
{

long long k;
matrix rezultat,baza;

fi>>k;
baza.a11=0;
baza.a12=1;
baza.a21=1;
baza.a22=1;

rezultat=ridicareLog(baza,k-2);


fo<<rezultat.a12+rezultat.a22;

    return 0;


}