#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

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

const int NMax = 2e6 + 5;
const int mod = 666013;

int K;

struct matrice22 {
    int a11,a12,a21,a22;
    matrice22() {
        matrice22(0,0,0,0);
    }
    matrice22(int a,int b,int c,int d) {
        a11 = a;
        a12 = b;
        a21 = c;
        a22 = d;
    }
};

struct matrice21 {
    int a1,a2;
    matrice21() {
        matrice21(0,0);
    }
    matrice21(int a,int b) {
        a1 = a;
        a2 = b;
    }
};
// matrice22 - matrice patratica de ordinul 2
// matrice21 - matrice cu 2 linii si o coloana

matrice21 prod(matrice22,matrice21);
matrice22 prod(matrice22,matrice22);
matrice22 pw(matrice22, int);
// functiile prod inmultesc 2 matrice
// pw(A,e) - ridica matricea A la puterea e in timp logaritmic

int main() {
    in>>K;

    matrice22 A(0,1,1,1);
    matrice21 first(0,1);

    matrice21 res = prod( pw(A,K), first );
    out<<res.a1;
    in.close();out.close();
    return 0;
}

matrice22 pw(matrice22 A, int e) {
    matrice22 res(1,0,0,1);
    while (e) {
        if (e % 2 == 1) {
            res = prod(res,A);
        }
        A = prod(A,A);
        e >>= 1;
    }
    return res;
}

matrice21 prod(matrice22 A,matrice21 M) {
    int top = (1LL * A.a11 * M.a1 + 1LL * A.a12 * M.a2) % mod,
        bot = (1LL * A.a21 * M.a1 + 1LL * A.a22 * M.a2) % mod;
    matrice21 res(top,bot);
    return res;
}

matrice22 prod(matrice22 A,matrice22 B) {
    int a11 = (1LL * A.a11 * B.a11 + 1LL * A.a12 * B.a21) % mod,
        a12 = (1LL * A.a11 * B.a12 + 1LL * A.a12 * B.a22) % mod,
        a21 = (1LL * A.a21 * B.a11 + 1LL * A.a22 * B.a21) % mod,
        a22 = (1LL * A.a21 * B.a12 + 1LL * A.a22 * B.a22) % mod;
    matrice22 res(a11,a12,a21,a22);
    return res;
}