#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long x[2][2],rez[2][2],aux[2][2],k;
void inmultire(long long a[][2],long long b[][2],long long c[][2]);
int main()
{
    fin>>k;
    k-=2;
    x[0][1]=x[1][0]=x[0][0]=1;
    rez[0][0]=rez[1][1]=1;
    while (k)
    {
        if (k%2==1)
        {
            inmultire(rez,x,aux); // x*rez si il pun in aux
            memcpy(rez,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        inmultire(x,x,aux);
        memcpy(x,aux,sizeof(aux));
        k/=2;
    }
    fout<<(rez[0][0]+rez[0][1])%MOD<<'\n';
    return 0;
}
void inmultire(long long a[][2],long long b[][2],long long c[][2])
{
    long long i,j,k;
    for (i=0; i<2; i++)
        for (j=0; j<2; j++)
        {
            c[i][j]=0;
            for (k=0; k<2; k++)
            {
                c[i][j]+=(a[i][k]*b[k][j]%MOD)%MOD;
                c[i][j]%=MOD;
            }
        }
}