#include<fstream>
#include<vector>

using namespace std;

const char iname[]="kfib.in";
const char oname[]="kfib.out";
const int mod=666013;

ifstream f(iname);
ofstream g(oname);

class matrix
{
    public:
    int n,m;
    vector<vector<int> >a;
    matrix()
    {
        n=m=0;
    }
    matrix(int x,int y)
    {
        n=x;m=y;
        a.resize(n);
        for(int i=0;i<n;++i)
            a[i].resize(m);
    }
    void resize(int x,int y)
    {
        n=x;m=y;
        a.resize(n);
        for(int i=0;i<n;++i)
            a[i].resize(m);
    }
    void operator=(const matrix& k)
    {
        this->resize(k.n,k.m);
        a=k.a;
    }
    vector<int> &operator[](const int& x)
    {
        return a[x];
    }
    matrix operator*(const matrix& d)
    {
        matrix k=d;
        int p=k.m;
        matrix aux(n,p);
        for(int i=0;i<n;++i)
            for(int j=0;j<p;++j)
                for(int r=0;r<m;++r)
                    aux[i][j]=(aux[i][j]+1LL*a[i][r]*k[r][j])%mod;

        return aux;
    }
} z(2,2),fib(1,2),aux(2,2),ans(2,2);

int n,i,step;

int main()
{
    f>>n;
    z.resize(2,2);
    z[0][0]=0;
    z[0][1]=1;
    z[1][1]=z[1][0]=1;
    fib[0][0]=0;
    fib[0][1]=1;
    aux=z;
    ans[0][0]=ans[1][1]=1;
    ans[1][0]=ans[0][1]=0;
    for(step=1;step<=n;step<<=1,z=z*z)
        if(step&n)
            ans=ans*z;
    fib=fib*ans;
    g<<fib[0][0]<<"\n";

    f.close();
    g.close();

    return 0;
}