#include <fstream>
#define nr 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
void inmultesteMatrici(long long int a[3][3],long long int b[3][3],long long int p[3][3])
{
    p[1][1]=a[1][1]*b[1][1]%nr+a[1][2]*b[2][1]%nr;
    p[1][1]%=nr;
    p[1][2]=a[1][1]*b[1][2]%nr+a[1][2]*b[2][2]%nr;
    p[1][2]%=nr;
    p[2][1]=a[2][1]*b[1][1]%nr+a[2][2]*b[2][1]%nr;
    p[2][1]%=nr;
    p[2][2]=a[2][1]*b[1][2]%nr+a[2][2]*b[2][2]%nr;
    p[2][2]%=nr;
}
void copiazaMatrice(long long int b[3][3],long long int a[3][3])
{
    for(int i=1; i<=2; ++i)
        for(int j=1; j<=2; ++j)
        {
            b[i][j]=a[i][j];
        }
}
long long int b[3][3],MatN[3][3],aux[3][3],Mat[3][3],K;
void lgput(long long int a[3][3],long long int n)
{
    MatN[1][1]=MatN[2][2]=1;
    MatN[1][2]=MatN[2][1]=0;
    copiazaMatrice(b,a);
    for(int i=0; n>>i; ++i)
    {
        if((n>>i)&1)
        {
            inmultesteMatrici(MatN,b,aux);
            copiazaMatrice(MatN,aux);
        }
        inmultesteMatrici(b,b,aux);
        copiazaMatrice(b,aux);
    }
}
int main()
{
    f>>K;
    Mat[1][1]=0;
    Mat[1][2]=Mat[2][1]=Mat[2][2]=1;
    lgput(Mat,K-1);
    g<<(MatN[1][1]%nr+MatN[1][2]%nr)%nr<<'\n';
return 0;
}