#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
#define MOD 666013
long long unsigned a[2][2] = {{0,1},{1,1}}, m[1][2] = {{1,1}},n,res[2][2], aux[2][2] = {{0,1},{1,1}};
void mul (long long unsigned a[2][2], long long unsigned b[2][2])
{
    unsigned i,j,k;
    long long unsigned c[2][2]={{0,0},{0,0}};
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
                c[i][j]+=a[i][k]%MOD * b[k][j]%MOD;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            a[i][j] = c[i][j];
}

void zero_res()
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            res[i][j] = 0;
}

void power (long long unsigned p)
{

    do
    {
        if(p%2==0)
            mul(a,a);
        else
        {
            mul(a,a);
            mul(a,aux);
        }
        p/=2;
       for(int i=0;i<2;i++)
        {for(int j=0;j<2;j++)
         cout<<a[i][j]<<' ';
         cout<<endl;}

        cout<<p<<"\n\n";

    }while(p>1);

}
long long unsigned better_power (long long unsigned F[2][2], long long unsigned p)
{
    if(p==1)
    {
        return F[0][1]+F[1][1];
    }
    better_power(F, p/2);
    mul(F,F);
    if(p%2==1)
    {
        mul(F,aux);
    }
    return F[0][1]+F[1][1];

}
long long unsigned find_nth ()
{
    fin>>n;
    if(n==0)
        return 0;
    if(n==1 || n ==2)
        return 1;
    return better_power(a, n-2);


}
int main()
{
    fout<<find_nth();


}