#include <iostream>
#include <fstream>
using namespace std;

ifstream f1("kfib.in");
ofstream f2("kfib.out");

unsigned long long MODULO = 666013;
class Matrix{
private:
    unsigned long long** a = NULL;
    int rows, columns;
public:

    Matrix(int rows, int columns){
        this->rows = rows;
        this->columns = columns;
        a = new unsigned long long* [rows];
        for(int i=0; i<rows;i++){
            a[i] = new unsigned long long [columns];
        }
        for(int i=0;i<rows;i++)
            for(int j=0;j<columns;j++)
                a[i][j]=0;
    }
    int getMatrixRows(){return rows;}
    int getMatrixCols(){return columns;}

    unsigned long long*& operator[] (const int &index) const {
        return a[index];
    }

    void operator= (const Matrix &other) {
        if (columns == other.columns && rows == other.rows) {
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < columns; j++)
                    a[i][j] = other.a[i][j];
        }
    }

    Matrix operator+ (const Matrix &other) const {
        if(columns == other.columns && rows == other.rows){
            Matrix temp(rows, columns);
            for(int i=0;i<rows;i++){
                for(int j=0;j<columns;j++){
                    temp[i][j] = a[i][j] + other[i][j];
                }
            }
            return temp;
        }
    }

    Matrix operator* (const Matrix &other) const {
        if(columns == other.rows){
            Matrix temp(rows, other.columns);
            for(int i=0; i<rows; i++){
                for(int j=0;j<other.columns; j++){
                    for(int c=0;c<columns;c++){
                        temp[i][j] = (temp[i][j] + (a[i][c]*other[c][j]))%MODULO;
                    }
                }
            }
            return temp;
        }
    }

    Matrix operator% (const unsigned long long &other) const {
        Matrix temp(rows, columns);
        for(int i=0;i<rows;i++){
            for(int j=0;j<columns;j++){
                temp[i][j] = a[i][j]%other;
            }
        }
        return temp;
    }

};

Matrix ridPutLog(Matrix matrice, unsigned long long power){

    if(power == 1){
        return matrice;
    }
    if(power%2!=0){
        power--;
        Matrix factor(matrice.getMatrixRows(), matrice.getMatrixCols());
        factor=matrice%MODULO;
        return (factor*ridPutLog(matrice*matrice%MODULO, power/2))%MODULO;
    }
    return ridPutLog(matrice*matrice%MODULO, power/2)%MODULO;
}

int main() {
    unsigned long long k;
    f1>>k;
    Matrix temp(2,2);
    Matrix original(2,2);
    original[0][0]=0;original[0][1]=1;original[1][0]=1;original[1][1]=1;
    temp = ridPutLog(original,k-1);
    Matrix init(2,1);
    init[0][0]=1;
    init[1][0]=1;
    f2<<(temp*init)[0][0];
    return 0;
}