#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define min(a,b)((a<b)?a:b)
#define max(a,b)((a>b)?a:b)
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
long long q,w,k,i,j,a[2][2]={{0,1},{1,1}},r[2][2][2]={{{0,1},{1,1}},{{0,1},{1,1}}};bool x;
#define rm(q,w)r[!x][q][w]=(r[x][q][0]*r[x][0][w]+r[x][q][1]*r[x][1][w])%666013
#define ro(q,w)r[!x][q][w]=(a[q][0]*r[x][0][w]+a[q][1]*r[x][1][w])%666013

void f(int k){
if(k>1)
    if(k&1){
        f(k>>1);
        x=!x;rm(0,0);rm(0,1);rm(1,0);rm(1,1);
        x=!x;ro(0,0);ro(0,1);ro(1,0);ro(1,1);
    }
        else{
        f(k>>1);
        x=!x;rm(0,0);rm(0,1);rm(1,0);rm(1,1);
    }
}
int main()
{
in>>k;f(k);
out<<r[!x][1][0];
}