#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);
                c[i][j] = c[i][j]%MOD;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            a[i][j] = c[i][j];
}

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();
}