#include <fstream>
#define MOD 666013
using namespace std;

ifstream in("kfib.in");

class matrix{
    long long a, b, c, d;
public:
    matrix(long long aa = 1, long long bb = 0, long long cc = 0, long long dd = 1) : a(aa), b(bb), c(cc), d(dd){}
    long long getB() const {
        return b;
    }
    matrix operator * (const matrix& other) const {
        matrix temp;
        temp.a = (a * other.a % MOD + b * other.c % MOD) % MOD;
        temp.b = (a * other.b % MOD + b * other.d % MOD) % MOD;
        temp.c = (c * other.a % MOD + d * other.c % MOD) % MOD;
        temp.d = (c * other.b % MOD + d * other.d % MOD) % MOD;

        return temp;
    }
};

matrix pow(long long n){
    matrix I, F(1, 1, 1, 0);
    while (n){
        if(n & 1)
            I = I * F;
        F = F * F;
        n >>= 1;
    }
    return I;
}

long long n;

int main() {
    in >> n;
    in.close();

    ofstream out("kfib.out");
    out << pow(n).getB();
    out.close();
    return 0;
}