#include <bits/stdc++.h>
using namespace std;

const long long MOD = 666013;

long long a[3][3], b[3][3], id[3][3];

void inmultire(long long a[3][3], long long b[3][3]) {
    long long c[3][3];
    for(int i = 1; i <= 2; i++) {
        for(int j = 1; j <= 2; j++) {
            c[i][j] = 0;
        }
    }
    for(int i = 1; i <= 2; i++) {
        for(int j = 1; j <= 2; j++) {
            for(int k = 1; k <= 2; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    for(int i = 1; i <= 2; i++) {
        for(int j = 1; j <= 2; j++) {
            a[i][j] = c[i][j];
        }
    }
}

int main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int k;
    cin >> k;
    id[1][1] = id[2][2] = 1;
    b[1][1] = b[1][2] = 1;
    a[1][2] = a[2][1] = a[2][2] = 1;
    k = k - 2;
    while(k > 0) {
        if(k % 2 == 1) {
            inmultire(id, a);
            k--;
        } else {
            inmultire(a, a);
            k /= 2;
        }
    }
    inmultire(b, id);
    cout << b[1][2];
    return 0;
}