#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

int n, p, i, j;
long long f[3][3], constanta[3][3];


void InmultireMatrice(long long f[3][3], long long m[3][3]){
    long long a=(f[1][1]*m[1][1]+f[1][2]*m[2][1])%666013;
    long long b=(f[1][1]*m[1][2]+f[1][2]*m[2][2])%666013;
    long long c=(f[2][1]*m[1][1]+f[2][2]*m[2][1])%666013;
    long long d=(f[2][1]*m[1][2]+f[2][2]*m[2][2])%666013;
    f[1][1]=a;
    f[1][2]=b;
    f[2][1]=c;
    f[2][2]=d;
}


int main(){
    fin>>p;
    if(p<=2){
        fout<<1;
        return 0;
    }
    constanta[1][1]=1;
    constanta[1][2]=1;
    constanta[2][1]=1;
    constanta[2][2]=0;
    f[1][1]=1;
    f[1][2]=1;
    f[2][1]=1;
    f[2][2]=0;
    p-=2;
    while(p!=0){
        if(p%2==1){
            InmultireMatrice(f, constanta);
        }
        InmultireMatrice(constanta, constanta);
        p=p/2;
    }
    fout<<f[1][1];
}