#include <bits/stdc++.h>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int k;
const int mod=666013;
struct mat
{
    int a[3][3];
    mat()
    {
        memset(a,0,sizeof(a));
    }
};
mat prod(mat A,mat B)
{
    mat ans;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
          for(int k=0;k<2;k++)
              ans.a[i][j]=(ans.a[i][j]+1LL*A.a[i][k]*B.a[k][j])%mod;
    return ans;
}
mat lgp(int p,mat A)
{
   mat ans;
   ans.a[0][0]=ans.a[1][1]=1;
   while(p)
   {
       if(p&1)
       {
           ans=prod(ans,A);
           p--;
       }
       A=prod(A,A);
       p>>=1;
   }
   return ans;
}
mat M,Sol,aux;
int main()
{
    in>>k;
    M.a[0][0]=M.a[0][1]=M.a[1][0]=1;
    Sol.a[0][0]=1;
    Sol.a[1][0]=1;
    if(k>=2) {
    M=lgp(k-2,M);
    Sol=prod(M,Sol);
    }
    out<<Sol.a[0][0];
    return 0;
}