#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef unsigned long long mat[2][2];
mat a,b;
int k;
const int mod=666013;
void inmultire(mat a, mat b,mat c)
{
    mat aux;
    aux[0][0]=(a[0][0]*b[0][0]%mod+a[0][1]*b[1][0]%mod)%mod;
    aux[0][1]=(a[0][0]*b[0][1]%mod+a[0][1]*b[1][1]%mod)%mod;
    aux[1][0]=(a[1][0]*b[0][0]%mod+a[1][1]*b[1][0]%mod)%mod;
    aux[1][1]=(a[1][0]*b[0][1]%mod+a[1][1]*b[1][1]%mod)%mod;
    c[0][0]=aux[0][0];
    c[0][1]=aux[0][1];
    c[1][0]=aux[1][0];
    c[1][1]=aux[1][1];
}
void a_la_n(mat a, mat b,unsigned long long n)
{
    if(n==1)
    {
        b[0][0]=0;
        b[0][1]=b[1][0]=b[1][1]=1;
    }
    else if(n==0)
    {
        b[0][0]=b[1][1]=0;
        b[0][1]=b[1][0]=1;
    }
    else
    {
        mat c;
        a_la_n(a,c,n/2);
        if(n%2==0) inmultire(c,c,b);
        else
        {
            inmultire(c,c,b);
            inmultire(b,a,b);
        }
    }
}
int main()
{
    a[0][0]=0;
    a[0][1]=a[1][0]=a[1][1]=1;
    fin>>k;
    a_la_n(a,b,k-1);
    fout<<b[1][1]<<'\n';
    return 0;
}