#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

#define int long long
#define pii pair <int, int>

string filename = "kfib";

#ifdef LOCAL
    ifstream fin("input.in");
    ofstream fout("output.out");
#else
    ifstream fin(filename + ".in");
    ofstream fout(filename + ".out");
#endif

const int MOD = 666013;

struct Mat{
    int n, m;
    vector <vector <int>> mat;

    void init(int _n, int _m){
        n = _n, m = _m;
        mat = vector <vector <int>> (n + 1, vector <int> (m + 1, 0));
    }
};

Mat mult(Mat a, Mat b){
    Mat ans;
    ans.init(2, 2);

    for(int i = 1; i <= a.n; i++){
        for(int j = 1; j <= b.m; j++){
            for(int k = 1; k <= a.m; k++){
                (ans.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % MOD) %= MOD;
            }
        }
    }

    return ans;
}

Mat exp(Mat m, int k){
    Mat ans;
    ans.init(2, 2);

    ans.mat[1][1] = 1, ans.mat[1][2] = 0;
    ans.mat[2][1] = 0, ans.mat[2][2] = 1;

    for(int i = 0; i <= 30; i++){
        if(k & (1 << i)){
            ans = mult(ans, m);
        }
        m = mult(m, m);
    }

    return ans;
}

signed main(){

    int n;
    fin >> n;

    if(n == 0){
        fout << 0 << '\n';
        return 0;
    }else if(n == 1 || n == 2){
        fout << 1 << '\n';
        return 0;
    }

    Mat trans;
    trans.init(2, 2);

    trans.mat[1][1] = 0, trans.mat[1][2] = 1;
    trans.mat[2][1] = 1, trans.mat[2][2] = 1;

    trans = exp(trans, n - 2);

    Mat x;
    x.init(1, 2);
    x.mat[1][1] = 1, x.mat[1][2] = 1;

    x = mult(x, trans);

    fout << x.mat[1][2] << '\n';

    return 0;
}