#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int MOD = 666013;

vector<vector<int>> star(int n, int m, int p, vector<vector<int>> a, vector<vector<int>> b) {
    // a = n x m
    // b = m x p
    // c = n x p
    vector<vector<int>> c(n, vector<int>(p));
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < p; j ++) {
            for(int k = 0; k < m; k ++) {
                c[i][j] += a[i][k] * b[k][j] % MOD;
            }
        }
    }
    return c;
}

vector<vector<int>> lgpow(int p) {
    if(p == 0)
        return {
            {1, 0},
            {0, 1}
        };
    if(p % 2)
        return star(2, 2, 2, {
            {0, 1},
            {1, 1}
        }, lgpow(p - 1));
    vector<vector<int>> temp = lgpow(p / 2);
    return star(2, 2, 2, temp, temp);
}

signed main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int x; cin >> x;
    vector<vector<int>> a = lgpow(x - 1);
    vector<vector<int>> b = {{1, 1}};
    b = star(1, 2, 2, b, a);
    cout << b[0][0];
}