#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

const int MOD=666013;
const int NMAX=2;
int F[NMAX][NMAX];
int p[NMAX][NMAX];

void produs(int p[NMAX][NMAX],int a[NMAX][NMAX],int b[NMAX][NMAX])
{
    int m,c,aux[NMAX][NMAX];
    for(int i=0;i<NMAX;i++)
    {
        for(int k=0;k<NMAX;k++)
        {
            aux[i][k]=0;
            for(int j=0;j<NMAX;j++)
            {
                aux[i][k]=(aux[i][k]+((long long)a[i][j]*b[j][k]%MOD))%MOD;
            }
        }
    }
    for(int i=0;i<NMAX;i++)
        for(int k=0;k<NMAX;k++)
            p[i][k]=aux[i][k];
}

void lgput(int p[NMAX][NMAX],int n)
{
    while(n!=0)
    {
        if(n%2!=0)
        {
            produs(p,p,F);
        }
        produs(F,F,F);
        n=n/2;
    }
}

int main()
{
    int n;
    fin>>n;
    F[0][0]=F[0][1]=F[1][0]=1;
    F[1][1]=0;
    p[0][0]=p[1][1]=1;
    p[0][1]=p[1][0]=0;
    lgput(p,n-1);
    fout<<p[0][0];
    return 0;
}