#include <iostream>
#include <fstream>
#define nr 666013

using namespace std;

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

long long help[3][3], rez[3][3], k;
long long a11, a12, a21, a22;
void init()
{
   rez[1][2] = rez[2][1] = rez [2][2] = 1;
   help[1][2] = help[2][1] = help[2][2] = 1;
}

void read()
{
    in>>k;
    k--;
}

void multiply(bool opt)
{
    if(opt == true)
    {
        a11 = rez[1][1] * help[1][1] + rez[1][2] * help[2][1];
        a12 = rez[1][1] * help[1][2] + rez[1][2] * help[2][2];
        a21 = rez[2][1] * help[1][1] + rez[2][2] * help[2][1];
        a22 = rez[2][1] * help[1][2] + rez[2][2] * help[2][2];

        rez[1][1] = a11 % nr;
        rez[1][2] = a12 % nr;
        rez[2][1] = a21 % nr;
        rez[2][2] = a22 % nr;
    }
    else
    {
        a11 = help[1][1] * help[1][1] + help[1][2] * help[2][1];
        a12 = help[1][1] * help[1][2] + help[1][2] * help[2][2];
        a21 = help[2][1] * help[1][1] + help[2][2] * help[2][1];
        a22 = help[2][1] * help[1][2] + help[2][2] * help[2][2];

        help[1][1] = a11 % nr;
        help[1][2] = a12 % nr;
        help[2][1] = a21 % nr;
        help[2][2] = a22 % nr;
    }
}

void solve()
{
    for(short int i=0; (1<<i)<=k ;i++)
    {
        if(((1<<i) & k) != 0)
        {
            multiply(true);
        }
        multiply(false);
    }
}

void write()
{
    out<<rez[1][2];
}
int main()
{
    read();
    init();
    solve();
    write();
}