#include <iostream>
#include <fstream>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
typedef unsigned long long ull;
ull n,a[2][2],b[2][2],ii[2][2];
const int mod=666013;
void inm(ull a[2][2],ull b[2][2]){
    ull ii[2][2];
    ii[0][0]=(1LL*a[0][0]*b[0][0]%mod+1LL*a[0][1]*b[1][0]%mod)%mod;
    ii[0][1]=(1LL*a[0][0]*b[0][1]%mod+1LL*a[0][1]*b[1][1]%mod)%mod;
    ii[1][0]=(1LL*a[1][0]*b[0][0]%mod+1LL*a[1][1]*b[1][0]%mod)%mod;
    ii[1][1]=(1LL*a[1][0]*b[0][1]%mod+1LL*a[1][1]*b[1][1]%mod)%mod;
   for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            a[i][j] = ii[i][j];
}

void alb( ull a[2][2] ,ull i[2][2], ull n){
        while(n){
                if(n%2==1) {
                        inm(ii,a);
                        --n;}

                inm(a,a);
                n/=2;
            }
}

void read()
{
    in>>n;--n;

}
int main()
{
    a[0][0]=0;
    a[1][0]=1;
    a[0][1]=1;
    a[1][1]=1;

    ii[0][0]=1;
    ii[1][0]=0;
    ii[0][1]=0;
    ii[1][1]=1;

    b[0][0]=0;
    b[1][0]=1;
    b[0][1]=1;
    b[1][1]=1;
    read();
    alb(a,ii,n);
    out<<ii[1][1]%mod;out<<endl;
   /// out<<b[1][0];

    return 0;
}