#include <bits/stdc++.h>
#include <fstream>
#include <memory>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

#define mod 666013;

void mult(int a[2][2], int b[2][2], int c[2][2]) {
    for(int i = 0;i < 2;++i) {
        for(int j = 0;j < 2;++j) {
            c[i][j] = 0;
            for(int k = 0;k < 2;++k) {
                c[i][j] = ((long long)c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
            }
        }
    }
}

void solve(const int& n) {
    int id[2][2] = {{1, 0}, {0, 1}};
    int put[2][2] = {{0, 1}, {1, 1}};
    int temp[2][2];
    int fin[2][2] = {{1, 1}, {0, 0}};

    for(int i = 0;(1 << i) <= n;++i) {
        if((1 << i) & n) {
            mult(id, put, temp);
            memcpy(id, temp, sizeof(id));
        }
        mult(put, put, temp);
        memcpy(put, temp, sizeof(put));
    }

    mult(fin, id, temp);
    g<<temp[0][1];
}

int main() {
    int n;
    f>>n;
    solve(n - 2);
    
    return 0;
}