#include <bits/stdc++.h>

#define MOD 666013

using namespace std;

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

long long F[2][3], Z[3][3], c[3][3], copie[3][3];
int bin[1001], n, i, j, k, p;
long long K;

void ZxZ(long long a[3][3], long long b[3][3])
{
    for (i=0; i<=2; i++)
        for (j=0; 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][k]+=(a[i][j]*b[j][k])%MOD;

    for (i=1; i<=2; i++)
        for (j=1; j<=2; j++)
            a[i][j]=c[i][j];
}

void FxF(long long a[2][3], long long b[3][3])
{
    long long c[2][3];
    c[1][1]=c[1][2]=0;

    for (i=1; i<=1; i++)
        for (j=1; j<=2; j++)
            for (k=1; k<=2; k++)
                c[i][k]+=(a[i][j]*b[j][k])%MOD;
    a[1][1]=c[0][1];
    a[1][2]=c[1][2];
}

int main()
{
    fin>>K;
    F[1][1]=0;
    F[1][2]=1;
    copie[1][1]=0;
    copie[1][2]=copie[2][1]=copie[2][2]=1;
    Z[1][1]=1;
    Z[2][2]=1;
    K--;
    while (K)
    {
        n++;
        bin[n]=K%2;
        K/=2;
    }
    for (p=n; p>= 1;p--)
    {
        ZxZ(Z, Z);
        if (bin[p])
            ZxZ(Z, copie);
    }
    FxF(F, Z);
    fout<<F[1][2]<<endl;
    fout.close();
    fin.close();
    return 0;
}