#include <fstream>
#include <vector>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod=666013;
class matrice_patratica
{
    vector <vector<int>> mat;
public:
    matrice_patratica(int dimensiune)
    {
        mat.resize(dimensiune);
        for(int i=0;i<dimensiune;i++)
            mat[i].resize(dimensiune);
    }
    vector<int> & operator [](const int & linie)
    {
        return mat[linie];
    }
    matrice_patratica operator *(const matrice_patratica & other)const
    {
        matrice_patratica rezultat(2);
        for(int i=0;i<mat.size();i++)
        {
            for(int j=0;j<other.mat[i].size();j++)
            {
                for(int x=0;x<mat[i].size();x++)
                    rezultat[i][j]=(rezultat[i][j]+1LL*mat[i][x]*other.mat[x][j])%mod;
            }
        }
        return rezultat;
    }
};
int k;
matrice_patratica I_2(2);
matrice_patratica lg_pow(matrice_patratica x , int exponent)
{
    if(exponent==0)
    {
        return I_2;
    }
    matrice_patratica p=lg_pow(x,exponent/2);
    if(exponent%2==0)
    {
        return p*p;
    }
    else
    {
        return x*p*p;
    }
}
int main()
{
    fin>>k;
    matrice_patratica nou(2);
    nou[0][0]=1;
    nou[0][1]=1;
    nou[1][0]=1;
    nou[1][1]=0;

    I_2[0][0]=0;
    I_2[0][1]=1;
    I_2[1][0]=1;
    I_2[1][1]=0;

    matrice_patratica raspuns(2);
    raspuns=lg_pow(nou,k-1);
    fout<<raspuns[0][0];
    return 0;
}