/// kfib
#include <iostream>
#include <fstream>

#define mod 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

struct matrice {
    long long A[2][2];
    matrice() {
        for (int i=0;i<2;i++)
            for (int j=0;j<2;j++)
                A[i][j] = 0;
    }
    matrice(long long a, long long b, long long c, long long d) {
        A[0][0] = a;
        A[0][1] = b;
        A[1][0] = c;
        A[1][1] = d;
    }
    friend matrice operator *(matrice A, matrice B) {
        return matrice(((A.A[0][0]*B.A[0][0])%mod+(A.A[0][1]*B.A[1][0])%mod)%mod,
                       ((A.A[0][0]*B.A[0][1])%mod+(A.A[0][1]*B.A[1][1])%mod)%mod,
                       ((A.A[1][0]*B.A[0][0])%mod+(A.A[1][1]*B.A[1][0])%mod)%mod,
                       ((A.A[1][0]*B.A[0][1])%mod+(A.A[1][1]*B.A[1][1])%mod)%mod);
    }
};

int k;

matrice power(matrice Z, int pwr) {
    if (pwr == 1) return Z;
    if (pwr % 2 == 0) return power(Z*Z, pwr/2);
    return Z*power(Z*Z, (pwr-1)/2);
}

void read() {
    f>>k;
}

void solve() {
    matrice a = power(matrice(0,1,1,1), k-1);
    g<<a.A[1][1]%mod<<'\n';
}

int main() {

    read();
    solve();

    f.close(); g.close();
    return 0;
}