#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
void inmult (int a[5][5],int b[5][5],int c[5][5])
{
    int i,j,k;
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
            c[i][j]=0;
        }
    }
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
            for (k=1;k<=2;k++)
            {
                c[i][j]=(c[i][j]+(1LL*a[i][k]*b[k][j])%MOD)%MOD;
            }
        }
    }
}
void atribuie (int a[5][5],int b[5][5])
{
    int i,j;
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
            a[i][j]=b[i][j];
        }
    }
}
void afis (int a[5][5])
{
    int i,j;
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
            g<<a[i][j]<<" ";
        }
        g<<'\n';
    }
    g<<'\n';
}
int p[5][5],sol[5][5],t[5][5],n,lg,ok,i,solfin[5][5],val[5][5],j,k;
int main()
{
    f>>n;
    if (n==0)
    {
        g<<"0";
        return 0;
    }
    lg=log2(n);
    ok=0;
    p[1][1]=0;
    p[1][2]=1;
    p[2][1]=p[2][2]=1;
    for (i=0;i<=lg;i++)
    {
        if ((n&(1<<i))!=0)
        {
            if (ok==0)
            {
                ok=1;
                atribuie(sol,p);
            }
            else
            {
                inmult(sol,p,t);
                atribuie(sol,t);
            }
        }
        inmult(p,p,t);
        atribuie(p,t);
    }
    val[1][1]=0;
    val[1][2]=1;
    for (j=1;j<=2;j++)
    {
        for (k=1;k<=2;k++)
        {
            solfin[1][j]=(solfin[1][j]+(val[1][k]*sol[k][j]))%MOD;
        }
    }
    g<<solfin[1][1];
    return 0;
}