#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define VMAX 200005
#define MOD 666013
using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
struct matrice2_2{
long long int i1,i2;
long long int j1,j2;
};

matrice2_2 multiplica(matrice2_2 a, matrice2_2 b)
{
    matrice2_2 c;
    c.i1=(a.i1*b.i1+a.i2*b.j1)%MOD;
    c.i2=(a.i1*b.i2+a.i2*b.j2)%MOD;
    c.j1=(a.j1*b.i1+a.j2*b.j1)%MOD;
    c.j2=(a.j1*b.i2+a.j2*b.j2)%MOD;
    return c;
}

matrice2_2 fast_exponentiation(matrice2_2 k,int putere)
{
    if(putere==1)
        return k;
    else if(putere%2)
        return multiplica(k,fast_exponentiation(k,putere-1));
    else
    {
        matrice2_2 pp;
        pp=fast_exponentiation(k,putere/2);
        return multiplica(pp,pp);
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    long long int n,m,i,j,k,t,nr,maxim,minim,suma,hash_number;
    fin>>k;
    if(k==0)
        fout<<"0\n";
    else if(k==1)
        fout<<"1\n";
    else
    {
        k--;
        matrice2_2 kizma_balls;
        kizma_balls.i1=0;
        kizma_balls.i2=kizma_balls.j1=kizma_balls.j2=1;
        matrice2_2 kizma = fast_exponentiation(kizma_balls,k);
        fout<<kizma.j2<<'\n';
    }






    return 0;
}