#include <fstream>

using namespace std;

#define mod 666013

#define lint long long int

struct mat
{
    lint val[2][2];
};

mat operator*(const mat &a,const mat &b)
{
    mat rez;
    rez.val[0][0]=((a.val[0][0]*b.val[0][0])%mod+(a.val[0][1]*b.val[1][0])%mod)%mod;
    rez.val[0][1]=((a.val[0][0]*b.val[0][1])%mod+(a.val[0][1]*b.val[1][1])%mod)%mod;
    rez.val[1][0]=((a.val[1][0]*b.val[0][0])%mod+(a.val[1][1]*b.val[1][0])%mod)%mod;
    rez.val[1][1]=((a.val[1][0]*b.val[0][1])%mod+(a.val[1][1]*b.val[1][1])%mod)%mod;
    return rez;
}

mat ridica(mat &a,int n)
{
    mat rez;
    if(n==0)
    {
        rez.val[0][0]=1;
        rez.val[1][1]=1;
        rez.val[0][1]=0;
        rez.val[1][0]=0;
        return rez;
    }
    else if(n==1)
    {
        return a;
    }
    else if(n%2==0)
    {
        rez=ridica(a,n/2);
        return rez*rez;
    }
    else
    {
        rez=ridica(a,n-1);
        return rez*a;
    }
}

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

    int n;
    fin>>n;
    if(n==0)
    {
         fout<<"0\n";
         fin.close();
         fout.close();
         return 0;
    }
    n--;
    mat x;
    x.val[0][0]=0;
    x.val[0][1]=1;
    x.val[1][0]=1;
    x.val[1][1]=1;
    mat rez;
    rez=ridica(x,n);
    fout<<rez.val[1][1]<<'\n';
    fin.close();
    fout.close();
    return 0;
}