#include <fstream>

using namespace std;

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

#define MOD 666013
#define int long long int

int a,b,n,x,y,z,c,teste;

struct matrice
{
    int n,m,a[10][10];
};

matrice mat,init;

void afis (matrice a)
{
    for (int i=1; i<=a.n; i++)
    {
        for (int j=1; j<=a.m; j++)
        {
            fout<<a.a[i][j]<<' ';
        }
        fout<<'\n';
    }
}

matrice inmultire (matrice a, matrice b)
{
    matrice aux;
    int i,j,n=a.n,m=b.m,k,com=a.m;
    aux.n=n,aux.m=m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            aux.a[i][j]=0;
            for (k=1; k<=com; k++)
            {
                aux.a[i][j]+=a.a[i][k]*b.a[k][j];
                aux.a[i][j]%=MOD;
            }
        }
    }
    return aux;
}

matrice exp_rapida (matrice a, int n)
{
    if (n==1)
    {
        return a;
    }
    matrice aux=exp_rapida (a,n/2);
    if (n%2==0)
    {
        return inmultire(aux,aux);
    }
    else
    {
        return inmultire(inmultire(aux,aux),a);
    }
}

signed main()
{
    fin>>n;
    mat.a[1][1]=1;
    mat.a[1][2]=1;
    init.a[1][1]=init.a[1][2]=init.a[2][1]=1;
    mat.n=1;
    mat.m=init.n=init.m=2;
    matrice answer=inmultire(mat,exp_rapida(init,n-2));
    fout<<answer.a[1][1];
    return 0;
}