#include <cstdio>

using namespace std;
FILE* FIN=freopen("kfib.in","r",stdin);
FILE* FOUT=freopen("kfib.out","w",stdout);

struct arr
{
    long long a[2][2];
}s,m;

long long n;

void ump(arr &x)
{
    x.a[0][0]=0;
    x.a[0][1]=1;
    x.a[1][0]=1;
    x.a[1][1]=1;
}
long long multlc(int l,int c,arr m1,arr m2)
{
    long long i,sr=0;
    for(i=0;i<2;i++)
        sr+=m1.a[l][i]*m2.a[i][c];
    return sr;
}
arr multm(arr m1,arr m2)
{
    arr sol;
    long long i,j;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            sol.a[i][j]=multlc(i,j,m1,m2);
    return sol;
}
void mod(arr &x)
{
    long long i,j;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            x.a[i][j]%=666013;
}
int main()
{
    scanf("%lli",&n);
    ump(s);
    ump(m);
    for(n-=2;n;n>>=1,m=multm(m,m),mod(m))
        if(n%2)
        {
            s=multm(s,m);
            mod(s);
        }
    printf("%lli",s.a[1][1]);
    return 0;
}