#include <cstring>

#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

const int MOD = 666013;

int a[2][2], ans[2][2];

inline void Multiply(int a[2][2], int b[2][2], int rez[2][2]) {
    memset(rez, 0, 16);
    for (int i = 0; i <= 1; ++ i) {
        for (int j = 0; j <= 1; ++ j) {
            for (int k = 0; k <= 1; ++ k) {
                rez[i][j] = (rez[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    memcpy(a, rez, 16);
}

inline void Power(int m, int mat[2][2]) {
    int c[2][2], aux[2][2];
    memcpy(c, a, 16);
    mat[0][0] = mat[1][1] = 1;
    for (; m; m >>= 1) {
        if (m & 1) {
            Multiply(mat, c, aux);
        }
        Multiply(c, c, aux);
    }
}

int main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int n;
    cin >> n;
    a[0][0]=0;a[0][1]=1;
    a[1][0]=1;a[1][1]=1;
    Power(n-1,ans);
    cout << ans[1][1] << "\n";
    return 0;
}