#include <bits/stdc++.h>
using namespace std;
#define MOD 666013


class Matrix{
public:
    vector<vector<int>> mat;
    int n;
    Matrix(int size, bool flag = false) : n(size) {
        mat.assign(n, vi(n, 0));
        if (flag) {
            for (int i = 0; i < n; i++)
                mat[i][i] = 1;
        }
    }
    Matrix operator *(const Matrix &other)const{
        Matrix result(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    result.mat[i][j] = (result.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return result;
    }

    Matrix& operator *=(const Matrix &other){
        *this = *this * other;
        return *this;
    }

    Matrix pow(int64_t exponent){
        Matrix result(n, true), base = *this;
        while(exp){
            if(exp % 2 == 1){
                result *= base;
            }
            base *= base;
            exponent *= 2;
        }
        return result;
    }
};

void setMatrix(Matrix a){
    a.mat = {{1,1}, {1,0}};
}

int32_t Kth(Matrix a, int k){
    return a.pow(k - 1).mat[0][0];
}

int32_t main(void){
    int n;
    cin >> n;
    Matrix a;
    setMatrix(a);
    cout << Kth(a ,n);

}