#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=666013;
ifstream f("kfib.in");
ofstream g("kfib.out");
int a[3][3], b[3][3];
void inm (int a[3][3], int b[3][3])
{
    int c[3][3];
    for (int i=1; i<=2; ++i)
        for (int j=1; j<=2; j++)
        c[i][j]=0;
    for (int i=1; i<=2; i++)
    {
        for (int j=1; j<=2; j++)
        {
            for (int k=1; k<=2; k++)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    for (int i=1; i<=2; i++)
        for (int j=1; j<=2; j++)
        a[i][j]=c[i][j];
}
void power (int k)
{
    while (k)
    {
        if (k%2)
            inm (b, a);
        inm (a, a);
        k/=2;
    }
}
signed main ()
{
    int k;
    f >> k;
    if (k==0)
        g << 0;
    else if (k==1)
        g << 1;
    else
    {
        a[1][1]=0, a[1][2]=1, a[2][1]=1, a[2][2]=1;
        b[1][1]=1, b[2][2]=1;
        power (k-1);

        g << (b[2][2])%mod;
    }
}