#include <iostream>
#include <fstream>


using namespace std;

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

long long int k,mod=666013,m[5][5],v[5][5],aux[5][5],rez[5][5];

void matrix_equal(long long int m[][5],long long int rez[][5])
{
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            m[i][j]=rez[i][j];
        }
    }
}
void matrix_multi(long long int p[][5],long long int n[][5])
{
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            long long int sum=0;
            for(int k=1; k<=2; k++)
                sum=(sum+p[i][k]*n[k][j]%mod)%mod;
            aux[i][j]=sum;
        }
    }
    matrix_equal(p,aux);

}
void matrix_exp (long long int m[][5],long long int k)
{
    while(k)
    {
        if(k%2==1)
        {
            matrix_multi(rez,m);
        }


        matrix_multi(m,m);
        k/=2;
    }

}
long long int fibo(int k);
int main()
{
    fin>>k;
    if(k==0)
        fout<<"0";
    else if(k==1)
        fout<<"1";
    else
    {
        m[1][1]=1;
        m[1][2]=1;
        m[2][1]=1;
        m[2][2]=0;
        v[1][1]=1;
        v[2][1]=0;
        rez[1][1]=1;
        rez[1][2]=0;
        rez[2][1]=0;
        rez[2][2]=1;
        matrix_exp(m,k-1);
        fout<<rez[1][1]*v[1][1];

    }
    return 0;
}