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

const int MOD = 666013;

vector <vector <int>> mult (vector <vector <int>> a, vector <vector <int>> b) {
    vector <vector <int>> c (2, vector <int> (2, 0));
    c[0][0] = 1LL * a[0][0] * b[0][0] + 1LL * a[0][1] * b[1][0];
    c[0][1] = 1LL * a[0][0] * b[0][1] + 1LL * a[0][1] * b[1][1];
    c[1][0] = 1LL * a[1][0] * b[0][0] + 1LL * a[1][1] * b[1][0];
    c[1][1] = 1LL * a[1][0] * b[0][1] + 1LL * a[1][1] * b[1][1];
    c[0][0] %= MOD;
    c[0][1] %= MOD;
    c[1][0] %= MOD;
    c[1][1] %= MOD;
    return c;
}

vector <vector <int>> fastExpo(vector <vector <int>> a, int k) {
    vector <vector <int>> rez (2, vector <int> (2, 0));
    rez[0][0] = 1;
    rez[0][1] = 0;
    rez[1][0] = 0;
    rez[1][1] = 1;

    while (k > 0) {
        if (k % 2 == 1) {
            rez = mult(a, rez);
        }
        a = mult(a, a);
        k /= 2;
    }
    return rez;
}

signed main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    cin >> k;
    vector <vector <int>> a (2, vector <int> (2, 0));
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    a = fastExpo(a, k);
    cout << a[1][0];
    return 0;
}