#include <bits/stdc++.h>
#define MAX 2
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct matrix
{
    int val[MAX][MAX];
    matrix()
    {
        memset(val,0,sizeof(val));
    }
};
inline matrix operator *(matrix a,matrix b)
{
    int i,j,k;
    matrix ans;
    for(i=0;i<MAX;i++)
        for(j=0;j<MAX;j++)
        for(k=0;k<MAX;k++)
        ans.val[i][j]=(ans.val[i][j]+1LL*a.val[i][k]*b.val[k][j])%MOD;
    return ans;
}
matrix sol,m,v;
int p;
int main()
{
   fin>>p;
   if(p==0)
   fout<<0;
   else
    if(p==1)
    fout<<1;
   else
    if(p==2)
    fout<<1;
   else{
   p-=1;
   sol.val[0][0]=sol.val[1][1]=1;
   m.val[0][0]=m.val[0][1]=m.val[1][0]=1;
   while(p>0)
   {
       if(p%2==1)
        sol=sol*m;
       p/=2;
       m=m*m;
   }
   v.val[0][0]=1;
   v.val[1][0]=0;
   sol=sol*v;
   fout<<sol.val[0][0];
   }
}