#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
using Matrix = vector < vector < long long> >;
const long long mod = 666013;
const long long k = 2;

Matrix mult(Matrix A, Matrix B) {

    Matrix res(k+1,vector<long long>(k+1));///initalizare de vector
    for ( long long i = 1; i <= k; ++i)
        for ( long long j = 1; j <= k; ++j)
            for ( long long w = 1; w <= k ;++ w) {
                res[i][j] = (res[i][j] + A[i][w] *B[w][j])%mod;
            }
    return res;
}

Matrix pow(Matrix A, long long p) {
    if(p == 1)
        return A;
    if(p % 2==1)
            return mult(A,pow(A,p-1));
    Matrix X = pow(A,p/2);
    return mult(X,X);

}
 int main() {
    long long n;
    fin >> n;
    if(n == 1 or n == 2) {
        fout << 1;
        return 0;
    }
    Matrix T(k+1,vector < long long> (k+1));
    T[1][1] = 1; T[1][2] = 1;
    T[2][1] = 1; T[2][2] = 0;
    T = pow(T,n-2);
    vector < long long> f(3);
    f[1] = 1;
    f[2] = 1;
    long long res = 0;
    for ( long long i = 1; i <= k; ++i) {
        res = (res + T[i][1] * f[i])%mod;
    }
    fout << res;

}