#include <fstream>

using namespace std;
const int MOD = 666013;
using ll = long long;

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

void inmultire(ll a[3][3], ll b[3][3]) {
    ll c[3][3];
    for(int i = 0; i <= 1; i++) {
        for(int j = 0; j <= 1; j++) {
            c[i][j] = 0;
            for(int k = 0; k <= 1; k++) ///lin/col comuna
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
        }
    }
    a[0][0] = c[0][0], a[0][1] = c[0][1];
    a[1][0] = c[1][0], a[1][1] = c[1][1];
}

void logexp(ll a[3][3], int n) {
    ll p[3][3];
    p[0][0] = p[1][1] = 1;
    p[0][1] = p[1][0] = 0;
    for(int k = 1; k <= n; k <<= 1) {
        if(n & k)
            inmultire(p, a);
        inmultire(a, a);
    }
    a[0][0] = p[0][0], a[0][1] = p[0][1];
    a[1][0] = p[1][0], a[1][1] = p[1][1];
}

ll fib[3][3];
ll a[3][3];
signed main()
{
    int n;
    cin >> n;
    if(n == 0) {
        cout << 0;
        return 0;
    }
    fib[0][0] = fib[0][1] = 1; ///init mat de fibo, pt F[1]
    a[0][1] = a[1][0] = a[1][1] = 1; ///init pt mat de inm

    logexp(a, n - 1); ///inm la n-1
    inmultire(fib, a);
    cout << fib[0][0];
    return 0;
}