//#include "stdafx.h"

#include <fstream>

#include <cstdio>

#include <stdio.h>
#include<vector>

using namespace std;



#define min(a,b) (a>b?b:a)

#define max(a,b) (a<b?b:a)




FILE *fin, *fout;

unsigned long long k=666013;




unsigned long long a[2][2],b[2][2],n;

void mm(unsigned long long x[2][2],unsigned long long y[2][2], unsigned long long z[2][2]){
    unsigned long long c[2][2];
    c[0][0]=x[0][0]*y[0][0]+x[0][1]*y[1][0];
    c[0][1]=x[0][0]*y[0][1]+x[0][1]*y[1][1];
    c[1][0]=x[1][0]*y[0][0]+x[1][1]*y[1][0];
    c[1][1]=x[1][0]*y[0][1]+x[1][1]*y[1][1];
    for(int i=0;i<=1;++i)
        for(int j=0;j<=1;++j)
            z[i][j]=c[i][j]%k;
    }


void prep(){
   b[0][0]=1LL;
   b[1][1]=1LL;

   a[0][1]=1LL;
   a[1][1]=1LL;
   a[1][0]=1LL;

   for(int i=1;i<=n;i*=2){
       if(i&n)
           mm(a,b,b);
       mm(a,a,a);
       }

    }


int main()

    {



    fin=fopen( "kfib.in", "r");

    fout=fopen("kfib.out", "w");

    fscanf(fin,"%d",&n);
    prep();
    fprintf(fout,"%d", b[0][1]);

    fclose(fin);

    fclose(fout);

    return 0;

    }