#include <fstream>
#define MOD 666013
using namespace std;
ifstream  fin("kfib.in");
ofstream fout("kfib.out");
long long k,z[4][4],ans[4][4];

void inmultire_matrice(long long m1[4][4], long long m2[4][4])
{
    long long a,b,c,d;
    a=((m1[1][1]*m2[1][1])%MOD+(m1[1][2]*m2[2][1])%MOD)%MOD;
    b=((m1[1][1]*m2[1][2])%MOD+(m1[1][2]*m2[2][2])%MOD)%MOD;
    c=((m1[2][1]*m2[1][1])%MOD+(m1[2][2]*m2[2][1])%MOD)%MOD;
    d=((m1[2][1]*m2[1][2])%MOD+(m1[2][2]*m2[2][2])%MOD)%MOD;

    m1[1][1]=a;
    m1[1][2]=b;
    m1[2][1]=c;
    m1[2][2]=d;
}

void fast_exp(long long e)
{
    ans[1][1]=0;
    ans[1][2]=ans[2][1]=ans[2][2]=1;

    while(e>0)
    {
        if(e%2==1)
        {
            inmultire_matrice(ans,z);
        }

        inmultire_matrice(z,z);
        e=e/2;
    }
}

int main()
{
    fin>>k;

    if(k==0)
    {
        fout<< 0 << "\n";
        return 0;
    }

    if(k==1)
    {
        fout<< 1 << "\n";
        return 0;
    }

    z[1][1]=0;
    z[1][2]=z[2][1]=z[2][2]=1;

    fast_exp(k-1);

    fout<< ans[2][1] << "\n";

    return 0;
}