#include <iostream>
#include <fstream>
#include <climits>
#include <algorithm>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

const int mod = 666013;

struct matrice21 {
    long long a[3];
    matrice21() {
        matrice21(0,1);
    }
    matrice21(int x,int y) {
        a[1] = x;
        a[2] = y;
    }
};

struct matrice22 {
    long long a[3][3];
    matrice22() {
        matrice22(0,1,1,1);
    }
    matrice22(int x11,int x12,int x21,int x22) {
        a[1][1] = x11;
        a[1][2] = x12;
        a[2][1] = x21;
        a[2][2] = x22;
    }
};

matrice22 pw(matrice22,int);
matrice22 prod(matrice22,matrice22);
matrice21 prod(matrice22,matrice21);

int main() {
    int K;
    in>>K;

    matrice22 A(0,1,1,1);
    A = pw(A,K);

    matrice21 B(0,1);

    matrice21 fin = prod(A,B);
    int result = fin.a[1];
    out<<result<<'\n';

    in.close();out.close();
    return 0;
}

matrice22 pw(matrice22 B,int e) {
    matrice22 res(1,0,0,1);

    while (e) {
        if (e%2 == 1) {
            res = prod(res,B);
        }
        B = prod(B,B);
        e >>= 1;
    }

    return res;
}

matrice22 prod(matrice22 A,matrice22 B) {
    matrice22 res(0,0,0,0);

    for (int i=1;i<=2;++i) {
        for (int j=1;j<=2;++j) {
            for (int k=1;k<=2;++k) {
                res.a[i][j] += (A.a[i][k] * B.a[k][j]) % mod;
            }
        }
    }

    return res;
}

matrice21 prod(matrice22 A,matrice21 B) {
    matrice21 res(0,0);

    for (int i=1;i<=2;++i) {
        for (int k=1;k<=2;++k) {
            res.a[i] = (A.a[i][k] * B.a[k]) % mod;
        }
    }

    return res;
}