#include <iostream>
#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
 int n,m[5][5],aux[5][5];

void Mult(int m1[5][5],int l1,int c1,int m2[5][5],int l2,int c2)
{ int i,j,t,m3[5][5];
     memset(m3,0,sizeof(m3));
    for(i=1;i<=l1;i++)
     for(j=1;j<=c2;j++)
      for(t=1;t<=l2;t++)
         m3[i][j]=(m3[i][j]+1LL*m1[i][t]*m2[t][j])%mod;

   for(i=1;i<=l1;i++)
    for(j=1;j<=c2;j++)
     m1[i][j]=m3[i][j];
}

void LgPut(int mat[5][5],int p)
{ int i,j,res[5][5];
    for(i=1;i<=2;i++)
     for(j=1;j<=2;j++)
      if (i==j) res[i][j]=1; else res[i][j]=0;

    for(i=0;i<=31;i++)
    {if (p&(1LL<<i)) Mult(res,2,2,mat,2,2);
     Mult(mat,2,2,mat,2,2);
    }

   for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
     mat[i][j]=res[i][j];
}

int main()
{ int i,j;
    f>>n;
    if (n<=1) g<<n<<"\n";
    else
    {
    m[1][1]=0; m[1][2]=1;
    aux[1][1]=0; aux[1][2]=1;
    aux[2][1]=1; aux[2][2]=1;

     LgPut(aux,n);
     Mult(m,1,2,aux,2,2);
     g<<m[1][1];

    }
    return 0;
}