#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void matin(long long A[2][2], long long B[2][2]) {
    long long C[2][2];
    C[0][0]=(A[0][0]*B[0][0]+A[0][1]*B[1][0])%666013;
    C[0][1] = (A[0][0]*B[0][1]+A[0][1]*B[1][1])%666013;
    C[1][0] = (A[1][0]*B[0][0]+A[1][1]*B[1][0])%666013;
    C[1][1] = (A[1][0]*B[0][1]+A[1][1]*B[1][1])%666013;

    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            A[i][j]=C[i][j];
        }
    }
}

void rp(long long mat[2][2], long long n) {
    long long rez[2][2]={{1,0},{0,1}};
    long long e[2][2];
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            e[i][j]=mat[i][j];
        }
    }

    while (n > 0) {
        if (n & 1) {
            matin(rez, e);
        }
        matin(e, e);
        n >>= 1;
    }

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            mat[i][j] = rez[i][j];
        }
    }
}

int main()
{
    long long k;
    fin>>k;
    long long fib[2][2]={{1,1},{1,0}};
    if(k==0){
        fout<<0<<endl;
    }
    else{
        rp(fib,k-1);
        fout<<fib[0][0]<<'\n';
    }
    return 0;
}