#include <cstdio>

using namespace std;

long long a[3][3]={0,0,0,0,0,1,0,1,1}, r[3][3]={0,0,0,0,0,1,0,1,1};
int k;
const int m=666013;

void inm(long long a[3][3],long long b[3][3])
{
    long long x1, x2, x3, x4;
    x1=(a[1][1]*b[1][1])%m+(a[1][2]*b[2][1])%m;
    x2=(a[1][1]*b[1][2])%m+(a[1][2]*b[2][2])%m;
    x3=(a[2][1]*b[1][1])%m+(a[2][2]*b[2][1])%m;
    x4=(a[2][1]*b[2][1])%m+(a[2][2]*b[2][2])%m;
    a[1][1]=x1%m;
    a[1][2]=x2%m;
    a[2][1]=x3%m;
    a[2][2]=x4%m;
}

void putere(int k)
{
    if (k==1)
    {
        inm(r,a);
        return;
    }
    if (k%2)
    {
        inm(r,a);
        putere(k-1);
    }
    else
    {
        inm(a,a);
        putere(k/2);
    }
}

int main()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    scanf ("%d ",&k);
    k-=2;
    putere(k);
    printf ("%lld\n",r[2][2]);
    return 0;
}