#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
int n,a[3][3],b[3][3],c[3][3],i[3][3];
const int mod=666013;

void produs (int a[3][3],int b[3][3],int c[3][3])
{
    c[1][1]=(1ll*a[1][1]*b[1][1]+1ll*a[1][2]*b[2][1])%mod;
    c[1][2]=(1ll*a[1][1]*b[1][2]+1ll*a[1][2]*b[2][2])%mod;
    c[2][1]=(1ll*a[2][1]*b[1][1]+1ll*a[2][2]*b[2][1])%mod;
    c[2][2]=(1ll*a[2][1]*b[1][2]+1ll*a[2][2]*b[2][2])%mod;
}

void copiere(int a[3][3],int b[3][3])
{
    a[1][1]=b[1][1];
    a[1][2]=b[1][2];
    a[2][1]=b[2][1];
    a[2][2]=b[2][2];
}

void plog (int n,int a[3][3])
{
    if (n==1)
        return;
    plog(n/2,a);
    produs(a,a,b);
    if (n%2!=0)
        produs(b,i,a);
    else
        copiere (a,b);
}

int main()
{
    fin>>n;
    i[1][1]=i[1][2]=i[2][1]=a[1][1]=a[1][2]=a[2][1]=1;
    if (n>2)
    {
        plog (n-2,a);
        fout<<(a[1][1]+a[1][2])%mod;
    }
    else
        fout<<1;
    return 0;
}