#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long m[3][3],e[3][3],n;
void inmultire(int x)
{
    long long a[3][3],b[3][3];
	if(x==1)
    {
        a[1][1]=b[1][1]=m[1][1];
        a[1][2]=b[1][2]=m[1][2];
        a[2][1]=b[2][1]=m[2][1];
        a[2][2]=b[2][2]=m[2][2];
        m[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%666013;
        m[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%666013;
        m[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%666013;
        m[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%666013;
    }
    else if(x==0)
    {
        a[1][1]=e[1][1];
        b[1][1]=m[1][1];
        a[1][2]=e[1][2];
        b[1][2]=m[1][2];
        a[2][1]=e[2][1];
        b[2][1]=m[2][1];
        a[2][2]=e[2][2];
        b[2][2]=m[2][2];
        e[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%666013;
        e[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%666013;
        e[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%666013;
        e[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%666013;
    }
    else
    {
        a[1][1]=m[1][1];
        b[1][1]=e[1][1];
        a[1][2]=m[1][2];
        b[1][2]=e[1][2];
        a[2][1]=m[2][1];
        b[2][1]=e[2][1];
        a[2][2]=m[2][2];
        b[2][2]=e[2][2];
        m[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%666013;
        m[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%666013;
        m[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%666013;
        m[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%666013;
    }
}
int putere(int p)
{
	while(p)
	{
	    if(p==1)
        {
            p--;
            break;
        }
		if(p&1)
		{
			inmultire(0);
			p--;
			inmultire(1);
		}
		else
		{
			inmultire(1);
		}
		p/=2;
	}
	/*for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            g<<m[i][j]<<" ";
        }
        g<<'\n';
    }
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            g<<e[i][j]<<" ";
        }
        g<<'\n';
    }*/
	inmultire(2);
}
int main()
{
	f>>n;
	if(n==0)
	{
		g<<0;
		return 0;
	}
	if(n==1)
	{
		g<<1;
		return 0;
	}
	n=n-1;
	m[1][1]=0;
	m[1][2]=1;
	m[2][1]=1;
	m[2][2]=1;
	e[1][1]=1;
	e[1][2]=0;
	e[2][1]=0;
	e[2][2]=1;
	putere(n);
	g<<m[2][2];
	return 0;
}