#include <bits/stdc++.h>

#define ull unsigned long long

using namespace std;

ull x[][2] = {0, 1, 1, 1}, y[][2] = {0, 1, 1, 1};

void inmultire(ull a[][2], ull b[][2]) {
    ull cpy[2][2];
    
    cpy[0][0] = a[0][0] * b[0][0] % 666013 + a[0][1] * b[1][0] % 666013;
    cpy[0][1] = a[0][0] * b[0][1] % 666013 + a[0][1] * b[1][1] % 666013;
    cpy[1][0] = a[1][0] * b[0][0] % 666013 + a[1][1] * b[1][0] % 666013;
    cpy[1][1] = a[1][0] * b[0][1] % 666013 + a[1][1] * b[1][1] % 666013;
    
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            b[i][j] = cpy[i][j] % 666013;
    
    return;
}

void exponentiere(int n) {
    if (n > 1) {
        exponentiere(n / 2);
        inmultire(y, y);
        
        if (n % 2)
            inmultire(x, y);
    }
    
    return;
}

int main(void) {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    
    int n;
    cin >> n;
    
    exponentiere(n - 1);
        
    cout << y[1][1];

    return 0;
}