#include <fstream>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

const int mod = 666013;
long long mat[3][3],m[3][3];

void inmultire(long long m1[][3],long long m2[][3])
{
    int i,j,k;
    long long aux[3][3]={};
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            for(k=1;k<=2;k++)
            {
                aux[i][j]+=(m1[i][k]*m2[k][j])%mod;
            }
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            mat[i][j]=aux[i][j]%mod;
}

void putere(int p)
{
    if(p==1)
    {
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                mat[i][j]=m[i][j];
    }
    else
    {
        if(p%2==0)
        {
            putere(p/2);
            inmultire(mat,mat);
        }
        else
        {
            putere(p-1);
            inmultire(m,mat);
        }
    }
}

int main()
{
	int n;
	cin >> n;
	m[2][1]=1;
	m[1][2]=1;
	m[2][2]=1;
    putere(n-2);
    cout<<(mat[1][2]+mat[2][2])%mod<<'\n';
	return 0;
}