#include <fstream>
#define nmax 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
unsigned long long z[2][2]={ {0, 1}, {1, 1} }, y[2][2], t[2][2], k;
void copy_matrix(unsigned long long old_m[2][2], unsigned long long new_m[2][2])
{
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++ j)
        {
            new_m[i][j] = old_m[i][j];
        }
}
void powerCalculus(unsigned long long p)
{
    copy_matrix(z, y);
    while(p > 0)
        if(p%2 == 0)
        {
            t[0][0] = (y[0][0] * y[0][0] + y[0][1] * y[1][0])%nmax;
            t[0][1] = (y[0][0] * y[0][1] + y[0][1] * y[1][1])%nmax;
            t[1][0] = (y[1][0] * y[0][0] + y[1][1] * y[1][0])%nmax;
            t[1][1] = (y[1][0] * y[0][1] + y[1][1] * y[1][1])%nmax;
            copy_matrix(t, y);
            p /= 2;
        }
        else
        {
            t[0][0] = (z[0][0] * y[0][0] + z[0][1] * y[1][0])%nmax;
            t[0][1] = (z[0][0] * y[0][1] + z[0][1] * y[1][1])%nmax;
            t[1][0] = (z[1][0] * y[0][0] + z[1][1] * y[1][0])%nmax;
            t[1][1] = (z[1][0] * y[0][1] + z[1][1] * y[1][1])%nmax;
            copy_matrix(t, z);
            p --;
        }
}
int main ()
{
    f >> k;
    powerCalculus(k - 2);
    g << z[1][1];
}