#include<bits/stdc++.h>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout("kfib.out");
long long m[4][4],f[4][4],sol[4][4],mod=666013;

void inm_mat (long long a[4][4],long long b[4][4])
{
    long long s,i,j,k,c[4][4];
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
    {
        s=0;
        for (k=1;k<=2;k++)
            s+=a[i][k]*b[k][j];
        s%=mod;
        c[i][j]=s;
    }
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
            a[i][j]=c[i][j];
}

void lgput (long long exp)
{
    while (exp!=0)
    {
        if (exp%2==1)
            inm_mat(sol,m);
        exp/=2;
        inm_mat(m,m);
    }
}

int main ()
{
    long long  k;
    fin>>k;
    if (k==0)
    {
        fout<<0<<'\n';
        exit(0);
    }
    m[1][2]=1;
    m[2][1]=1,m[2][2]=1;
    f[1][1]=0,f[1][2]=1;
    sol[1][1]=1,sol[2][2]=1;
    lgput(k-1);
    inm_mat(f,sol);
    fout<<f[1][2]<<'\n';
    return 0;
}