#include <bits//stdc++.h>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int mod=666013;
int a[3][3], r[3][3];
int n;
void initialization()
{
    a[1][1]=0;
    a[2][2]=1;
    a[1][2]=1;
    a[2][1]=1;
    r[1][1]=0;
    r[1][2]=1;
}
void multipli_matrix(int x[3][3], int y[3][3])
{
    int c[3][3]={};
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {//calculez elementul de pe pozitia i,j din matricea c
            for(int k=1; k<=2; k++)
            {
                c[i][j]=(c[i][j]+(1ll*x[i][k]*y[k][j])%mod)%mod;
            }
        }
    }
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            x[i][j]=c[i][j];
        }
    }
}
void lgput(int putere)
{
    while(putere)
    {
        if(putere%2==1)
        {
            multipli_matrix(r, a);
        }
        multipli_matrix(a, a);
        putere/=2;
    }
}
int main()
{
    int n;
    in>>n;
    initialization();
    lgput(n-1);
    out<<r[1][2];
}