#include <bits/stdc++.h>

using namespace std;

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

void putere(int k) {
    a[1][1] = a[2][1] = a[1][2] = 1;
    b[1][1] = b[2][2] = 1; b[1][2] = b[2][1] = 0;

    long long c[3][3]; // aux
    while(k) {
        if(k & 1) {
            c[1][1] = a[1][1] * b[1][1] + a[1][2] * b[2][1];
            c[1][2] = a[1][1] * b[1][2] + a[1][2] * b[2][2];
            c[2][1] = a[2][1] * b[1][1] + a[2][2] * b[2][1];
            c[2][2] = a[2][1] * b[1][2] + a[2][2] * b[2][2];
            b[1][1] = c[1][1] % 666013;
            b[1][2] = c[1][2] % 666013;
            b[2][1] = c[2][1] % 666013;
            b[2][2] = c[2][2] % 666013;
        }
        c[1][1] = a[1][1] * a[1][1] + a[1][2] * a[2][1];
        c[1][2] = a[1][1] * a[1][2] + a[1][2] * a[2][2];
        c[2][1] = a[2][1] * a[1][1] + a[2][2] * a[2][1];
        c[2][2] = a[2][1] * a[1][2] + a[2][2] * a[2][2];
        a[1][1] = c[1][1] % 666013;
        a[1][2] = c[1][2] % 666013;
        a[2][1] = c[2][1] % 666013;
        a[2][2] = c[2][2] % 666013;
        k >>= 1;
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    int k;
    cin >> k;
    if(k < 2) {
        cout << "1\n";
        return 0;
    }
    k -= 2;
    putere(k); //matricea
    cout << (b[1][1] + b[2][1]) % 666013 << "\n";
    return 0;
}