#include <iostream>
#include <fstream>
using namespace std;
int n;
const int M=666013;
unsigned long long A[3][3];
void Put(unsigned long long X[3][3],unsigned long long n);
void Prod(unsigned long long a[3][3],unsigned long long b[3][3],unsigned long long c[3][3]);
void Atr(unsigned long long a[3][3],unsigned long long b[3][3]);
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    in>>n;
    A[1][2]=A[2][1]=A[2][2]=1;
    Put(A,n-2);
    out<<A[2][2]<<"\n";
    out.close();
    in.close();
    return 0;
}
void Put(unsigned long long fin[3][3],unsigned long long N)
{unsigned long long P[3][3]; Atr(P,fin);unsigned long long aux[3][3];
    while (N>0)
    {
        if (N%2==1)
            {Prod(fin,P,aux);
            Atr(fin,aux);}
        N/=2;
        Prod(P,P,aux);Atr(P,aux);
    }
}
void Prod(unsigned long long a[3][3],unsigned long long b[3][3],unsigned long long c[3][3])
{int i,j,z;c[1][1]=c[1][2]=c[2][1]=c[2][2]=0;
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
          for (z=1;z<=2;z++)
          {
              c[i][j]+=((a[i][z]*b[z][j])%M);
          }
        }
    }
}
void Atr(unsigned long long a[3][3],unsigned long long b[3][3])
{int i,j;
    for (i=0;i<=2;i++)
        for (j=0;j<=2;j++)
        a[i][j]=b[i][j];
}