#include <iostream>
#include <fstream>
using namespace std;

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

long long m[2][3],a[3][3],b[3][3],n,mfinal[2][3],aux[3][3];
/*
(f1 f2) * ((0 1)(1 1)) = (f2 f3)
(f1 f2) * ((0 1)(1 1)) * ((0 1)(1 1)) = (f3 f4)
...
(f1 f2) * (((0 1)(1 1))) ^ (n-1) = (fn fn+1)
*/
const int modulo=666013;

void afisare(int x[3][3])
{
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
            out<<x[i][j]<<" ";
        out<<endl;
    }
    out<<endl;
}

void inmultire(long long x[3][3],long long  y[3][3],long long z[3][3])
{
    aux[1][1]=((x[1][1]*y[1][1])%modulo+(x[1][2]*y[2][1])%modulo)%modulo;
    aux[1][2]=(x[1][1]*y[1][2]%modulo+x[1][2]*y[2][2]%modulo)%modulo;
    aux[2][1]=(x[2][1]*y[1][1]%modulo+x[2][2]*y[2][1]%modulo)%modulo;
    aux[2][2]=(x[2][1]*y[1][2]%modulo+x[2][2]*y[2][2]%modulo)%modulo;
    z[1][2]=aux[1][2];
    z[1][1]=aux[1][1];
    z[2][1]=aux[2][1];
    z[2][2]=aux[2][2];

}
int main()
{
    int p;
    in>>n;
    p=n-1;
    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    aux[1][1]=0;
    aux[1][2]=aux[2][1]=aux[2][2]=1;
    b[1][1]=1;
    b[1][2]=0;
    b[2][1]=0;
    b[2][2]=1;
    m[1][1]=0;
    m[1][2]=1;
    while(p!=0)
    {
        if(p%2==1)
        {
            inmultire(b,a,b);
        }
        p=p/2;
        inmultire(a,a,a);
        //afisare(a);
        //afisare(b);
    }
    mfinal[1][2]=m[1][1]*b[1][2]+m[1][2]*b[2][2];
    /* while(i<n)
     {
         a[1][1]=a[1][1]*a[1][1]+a[1][2]*a[2][1];
         a[1][2]=a[1][1]*a[1][2]+a[1][2]*a[2][2];
         a[2][1]=a[2][1]*a[1][1]+a[2][2]*a[2][1];
         a[2][2]=a[2][1]*a[1][2]+a[2][2]*a[2][2];
         i++;
     }
     */
    out<<mfinal[1][2];
    return 0;
}