#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++)
        {
            int s=0;
            for (int k=1; k<=2; k++)
                s=s+(a[i][k]*b[k][j])%mod;
            c[i][j]=s;
        }
    }
    for (int i=1; i<=2; i++)
        for (int j=1; j<=2; j++)
        a[i][j]=c[i][j];

}
void power (int exp)
{
    while (exp)
    {
        if (exp%2)
            inm (b, a);
        inm (a, a);
        exp/=2;
    }
}
signed main ()
{
    a[1][1]=0, a[1][2]=1, a[2][2]=1, a[2][1]=1;
    b[1][1]=1, b[2][2]=1;
    int k;
    f >> k;
    if (k<2)
    {
        if (k==0)
            g << 0;
        else g<<1;
        exit(0);
    }
    power (k-1);
    g << (b[2][2])%mod;

}