#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 666013;

int a[3][3], b[3][3], p[3][3];

void inmultire(int a[3][3], int b[3][3]) {
    int 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;
            }
            //a[i][j] = c[i][j];
        }
    }
    for(int i = 1; i <= 2; i++) {
        for(int j = 1; j <= 2; j++) {
            a[i][j] = c[i][j];
        }
    }
}

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