#include <fstream>

using namespace std;

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

const int mod=666013;

struct matrice{
    long long int val[2][2];
};

matrice prod(matrice a, matrice b)
{
    matrice r;
    r.val[0][0]=(a.val[0][0]*b.val[0][0])%mod+(a.val[0][1]*b.val[1][0])%mod;
    r.val[0][1]=(a.val[0][0]*b.val[0][1])%mod+(a.val[0][1]*b.val[1][1])%mod;
    r.val[1][0]=(a.val[1][0]*b.val[0][0])%mod+(a.val[1][1]*b.val[1][0])%mod;
    r.val[1][1]=(a.val[1][0]*b.val[0][1])%mod+(a.val[1][1]*b.val[1][1])%mod;
    r.val[0][0]%=mod;
    r.val[0][1]%=mod;
    r.val[1][0]%=mod;
    r.val[1][1]%=mod;
    return r;
}

matrice exp(matrice b, int e)
{
    if(e==1) return b;
    if(e%2==1) return prod(b,exp(b,e-1));
    matrice p=exp(b, e/2);
    return prod(p,p);
}

int fib(int k)
{
    matrice M;
    M.val[0][0]=1;
    M.val[0][1]=1;
    M.val[1][0]=1;
    M.val[1][1]=0;
    M=exp(M, k);
    return M.val[0][1];
}

int main()
{
    int k;
    fin >> k;
    fout << fib(k);
    return 0;
}