#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int MOD = 666013;

struct sq2matrix {
    int a[2][2];

    sq2matrix mult(sq2matrix b) {
        sq2matrix c;
        c.a[0][0] = (a[0][0] * b.a[0][0] + a[0][1] * b.a[1][0]) % MOD;
        c.a[0][1] = (a[0][0] * b.a[0][1] + a[0][1] * b.a[1][1]) % MOD;
        c.a[1][0] = (a[1][0] * b.a[0][0] + a[1][1] * b.a[1][0]) % MOD;
        c.a[1][1] = (a[1][0] * b.a[0][1] + a[1][1] * b.a[1][1]) % MOD;
        return c;
    }
    sq2matrix power(int k) {
        sq2matrix c;
        c.a[0][0] = a[0][0];
        c.a[0][1] = a[0][1];
        c.a[1][0] = a[1][0];
        c.a[1][1] = a[1][1];
        if (k == 1) {
            return c;
        }
        c = power(k/2);
        c = c.mult(c);
        if (k % 2 == 1) {
            c = mult(c);
        }
        return c;
    }
};

struct lin2matrix {
    int a[2];

    lin2matrix mult(sq2matrix b) {
        lin2matrix c;
        c.a[0] = (a[0] * b.a[0][0] + a[1] * b.a[1][0]) % MOD;
        c.a[1] = (a[0] * b.a[0][1] + a[1] * b.a[1][1]) % MOD;
        return c;
    }
};

signed main() {
    int k;

    fin >> k;

    if (k <= 1) {
        fout << k;
        return 0;
    }

    sq2matrix mat;
    mat.a[0][0] = 0;
    mat.a[0][1] = 1;
    mat.a[1][0] = 1;
    mat.a[1][1] = 1;
    mat = mat.power(k - 1);

    lin2matrix fibonacci;
    fibonacci.a[0] = 0;
    fibonacci.a[1] = 1;
    fibonacci = fibonacci.mult(mat);

    fout << fibonacci.a[1];
    return 0;
}