#include <iostream>
#include <fstream>
using namespace std;

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

#define ll long long

ll** u;
const int MOD = 666013;

ll** create2dArray(int l, int c) {
    ll** arr = new ll*[l];
    for (int i = 0; i < l; ++i) {
        arr[i] = new ll[c];
    }

    return arr;
}

ll** multiply(ll** a, ll** b, ll l1 = 2, int c1 = 2, int l2 = 2, int c2 = 2) {
    ll** r;
    r = create2dArray(3, 3);
    for (int l = 1; l <= l1; ++l) {
        for (int c = 1; c <= c1; ++c) {
            r[l][c] = 0;
            for (int j = 1; j <= c1; ++j) {
                r[l][c] += (a[l][j] * b[j][c]) % MOD;
            }
            r[l][c] %= MOD;
        }
    }

    return r;
}

ll** pow(ll** z, int n) {
    if (n == 0) return u;
    if (n % 2 == 0) return pow(multiply(z, z), n / 2);
    return multiply(z, pow(z, n - 1));
}

int main()
{
    u = create2dArray(3, 3);
    u[1][1] = u[2][2] = 1;
    u[1][2] = u[2][1] = 0;

    ll** z;
    z = create2dArray(3, 3);
    z[1][1] = 0;
    z[1][2] = 1;
    z[2][1] = 1;
    z[2][2] = 1;

    int n;
    ll** r;
    in >> n;
    r = pow(z, n - 1);



    ll** a;
    a = create2dArray(2, 3);
    a[1][1] = 0;
    a[1][2] = 1;
    a = multiply(a, r, 1, 2);
    out << a[1][2];


    return 0;
}