#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
const int MOD=666013;
int a[3][3],r[3][3],r2[3][3],b[3][3];
void Inmultire2 ()
{
    r2[1][1]=(1LL*r[1][1]*a[1][1]+1LL*r[1][2]*a[2][1])%MOD;
    r2[1][2]=(1LL*r[1][1]*a[1][2]+1LL*r[1][2]*a[2][2])%MOD;
    r2[2][1]=(1LL*r[2][1]*a[1][1]+1LL*r[2][2]*a[2][1])%MOD;
    r2[2][2]=(1LL*r[2][1]*a[1][2]+1LL*r[2][2]*a[2][2])%MOD;
    r[1][1]=r2[1][1];
    r[1][2]=r2[1][2];
    r[2][1]=r2[2][1];
    r[2][2]=r2[2][2];
}
void Inmultire ()
{
    b[1][1]=a[1][1];
    b[1][2]=a[1][2];
    b[2][1]=a[2][1];
    b[2][2]=a[2][2];
    a[1][1]=(1LL*b[1][1]*b[1][1]+1LL*b[1][2]*b[2][1])%MOD;
    a[1][2]=(1LL*b[1][1]*b[1][2]+1LL*b[1][2]*b[2][2])%MOD;
    a[2][1]=(1LL*b[2][1]*b[1][1]+1LL*b[2][2]*b[2][1])%MOD;
    a[2][2]=(1LL*b[2][1]*b[1][2]+1LL*b[2][2]*b[2][2])%MOD;
}
void Ridicarelaputere (int k)
{
    r[1][2]=0;
    r[1][1]=1;
    r[2][1]=0;
    r[2][2]=1;
    while (k)
    {
        if (k%2==1)
        {
            Inmultire2 ();
        }
        Inmultire ();
        k=k/2;
    }
}
int main()
{
    int k;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    fin >>k;
    Ridicarelaputere (k-1);
    fout <<r[2][2];
    fin.close ();
    fout.close ();
    return 0;
}