#include <bits/stdc++.h>
using namespace std;
const int Mod=666013;
int k,A[3][3];
void inmultire(int a[3][3],int b[3][3],int c[3][3]);
void copiere(int a[3][3],int b[3][3]);
void make_A(int put);
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    in>>k;
    make_A(k-1);
    if (k<=3)
    {
        if (k==3)
            out<<"2\n";
        if (k==2)
            out<<"1\n";
        if (k==1)
            out<<"1\n";
    }
    else
    {
    int s,i;
    out<<A[2][2]%Mod<<"\n";
    }
}
void inmultire(int a[3][3],int b[3][3],int c[3][3])
{int i,j,z;
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
        c[i][j]=0;
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
          for (z=1;z<=2;z++)
                c[i][j]=1LL*c[i][j]+(1LL*a[i][z]*b[z][j]%Mod)%Mod;
}
void copiere(int a[3][3],int b[3][3])
{int i,j;
    for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
        a[i][j]=b[i][j]%Mod;

}
void make_A(int put)
{int aux[3][3],P[3][3],i,j;
    put--;
    A[2][1]=A[1][2]=A[2][2]=1;
        copiere(P,A);
    while (put>0)
    {
        if (put%2==1)
        {
            inmultire(A,P,aux);
            copiere(A,aux);
        }
        inmultire(P,P,aux);
        copiere(P,aux);
        put/=2;
    }
}