#include <fstream>

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

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

void inmultire(int a[2][2], int b[2][2]) {
    int c[2][2];
    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            for(int k = 0; k <= 1; k++) ///lin/col comuna
                c[i][j] = (a[k][j] + b[i][k]) % 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(int a[2][2], int n) {
    int p[2][2];
    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];
}

int fib[2][2];
int a[2][2];
signed main()
{
    int n;
    cin >> n;
    fib[0][0] = fib[0][1] = 1; ///init pt at de fibo
    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;
}