//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map> 
#include <map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <assert.h>
using namespace std;
const string file = "kfib";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
#define FAST ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
const int MOD = 666013;
struct mat2x2 {
    long long v00, v01, v10, v11;
};
struct mat2x1 {
    long long v00, v10;
};
mat2x2 inm(mat2x2 a, mat2x2 b) {
    mat2x2 c;
    c.v00 = (1LL * a.v00 * b.v00 + a.v01 * b.v10) % MOD;
    c.v01 = (1LL * a.v00 * b.v01 + a.v01 * b.v11) % MOD;
    c.v10 = (1LL * a.v10 * b.v00 + a.v11 * b.v10) % MOD;
    c.v11 = (1LL * a.v10 * b.v01 + a.v11 * b.v11) % MOD;
    return c;
}
mat2x1 inm(mat2x2 a, mat2x1 b) {
    mat2x1 c;
    c.v00 = (1LL * a.v00 * b.v00 + a.v01 * b.v10) % MOD;
    c.v10 = (1LL * a.v10 * b.v00 + a.v11 * b.v10) % MOD;
    return c;
}
mat2x2 ex(mat2x2 a, int pwr) {
    mat2x2 ans = a;
    pwr--;
    while (pwr) {
        if (pwr & 1) ans = inm(ans, a);
        a = inm(a, a);
        pwr >>= 1;
    }
    return ans;
}
int main(void)
{
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0;
        return 0;
    }
    else if (n == 1 || n == 2) {
        cout << 1;
        return 0;
    }
    else {

        mat2x2 ans = ex({ 0,1,1,1 }, n - 2);
        mat2x1 a = { 1,1 };
        cout << inm(ans, a).v10 % MOD;
    }

    return 0;
}