#include <iostream>
#define MOD 666013

using namespace std;

struct mat {
    long long a = 1, b = 0, c = 0, d = 1;
};

struct fib_mat {
    long long f1, f2;
};

mat mult(mat A, mat B) {
    mat R;
    R.a = (A.a * B.a + A.b * B.c) % MOD;
    R.b = (A.a * B.b + A.b * B.d) % MOD;
    R.c = (A.c * B.a + A.d * B.c) % MOD;
    R.d = (A.c * B.b + A.d * B.d) % MOD;
    return R;
}

mat lgput(mat Z1, int n) {
    mat R;
    while(n != 0) {
        if(n & 1)
          R = mult(R, Z1);
        Z1 = mult(Z1, Z1);
        n /= 2;
    }
    return R;
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    mat Z1;
    Z1.a = 0;
    Z1.b = 1;
    Z1.c = 1;
    Z1.d = 1;

    int N;
    cin >> N;

    Z1 = lgput(Z1, N);
    //cout << Z1.a << Z1.b << Z1.c << Z1.d;

    fib_mat f;
    f.f1 = 0;
    f.f2 = 1;

    fib_mat r;
    r.f1 = Z1.a * f.f1 % MOD + Z1.c * f.f2 % MOD;
    r.f2 = Z1.b * f.f1 % MOD + Z1.d * f.f2 % MOD;
    cout << r.f1;

    return 0;
}