#include<fstream>
using namespace std;


ifstream cin("kfib.in");
ofstream cout("kfib.out");
#define mod 666013
int N;
struct matrice{ int a11,a12,a21,a22; };
matrice mult(matrice A, matrice B){
   matrice C;
   C.a11 = A.a11*B.a11 + A.a12*B.a21; C.a11%=mod;
   C.a12 = A.a11*B.a12 + A.a12*B.a22; C.a12%=mod;
   C.a21 = A.a21*B.a11 + A.a22*B.a21; C.a21%=mod;
   C.a22 = A.a21*B.a12 + A.a22*B.a22; C.a22%=mod;
   return  C;
 }
matrice pow(matrice A, int N){
  if (N==1) return A;
  if (N&1) return  mult(pow(A,N-1),A);
  matrice B = pow(A,N/2);
  return  mult(B,B);
}

int main()
{
    cin >> N;
    //cout<<N<<'\n';
    matrice A = {0,1,1,1};
    matrice Init = {0,1,0,0};
    matrice RS = pow(A, N);
    RS = mult(Init, RS);
    cout << RS.a11;
    return 0;
}