#include <fstream>
#include <iostream>

using namespace std;

const int MOD = 666013;

long long n;



class matrix{
private:
    struct matrice{
        long long a, b, c, d;
        // a b
        // c d
    }mat;

public:

    matrix();
    matrix(long long _11, long long _12, long long _21, long long _22);

    long long get();

    matrix &operator *(const matrix &i);
    matrix &operator =(const matrix &i);
    matrix &operator ^(long long x);
    matrix &operator %(const int x);
    friend ostream &operator<< (ostream &cout, const matrix &i);
};

matrix& matrix ::operator*(const matrix &i) {

    long long A, B, C, D;

    A = ((this -> mat.a * i.mat.a) % MOD  + (this -> mat.b * i.mat.c) % MOD ) % MOD;
    B = ((this -> mat.a * i.mat.b) % MOD  + (this -> mat.b * i.mat.d) % MOD ) % MOD;
    C = ((this -> mat.c * i.mat.a) % MOD  + (this -> mat.d * i.mat.c) % MOD ) % MOD;
    D = ((this -> mat.c * i.mat.b) % MOD  + (this -> mat.d * i.mat.d) % MOD ) % MOD;

    this -> mat.a = A;
    this -> mat.b = B;
    this -> mat.c = C;
    this -> mat.d = D;
    return *this;

}

long long matrix ::get() {
    return this -> mat.a;
}

matrix& matrix ::operator%(const int x) {

    this -> mat.a = this -> mat.a % x;
    this -> mat.b = this -> mat.b % x;
    this -> mat.c = this -> mat.c % x;
    this -> mat.d = this -> mat.d % x;

    return *this;
}
matrix& matrix::operator^(long long x) {

    matrix P(1LL * 1, 1LL * 0, 1LL * 0, 1LL * 1);

    while(x != 1) {
        if (x % 2 == 1) {
            x--;
            P = (P * *this);
            P = P % MOD;
        }
        else{
            x /= 2;

            *this = (*this * *this);
            *this = *this % MOD;
        }
    }
    *this = *this * P;
    *this = *this % MOD;
    return *this;
}

matrix ::matrix() {
    this -> mat.a = this -> mat.b = this -> mat.c = this -> mat.d = 0;
}

matrix ::matrix(long long _11, long long _12, long long _21, long long _22) {
    this -> mat.a = _11;
    this -> mat.b = _12;
    this -> mat.c = _21;
    this -> mat.d = _22;
}

matrix& matrix::operator=(const matrix &i) {
    this -> mat.a = i.mat.a;
    this -> mat.b = i.mat.b;
    this -> mat.c = i.mat.c;
    this -> mat.d = i.mat.d;

    return *this;
}

ostream &operator<<(ostream &cout, const matrix &i){
    cout << i.mat.a << " " << i.mat.b << "\n";
    cout << i.mat.c << " " << i.mat.d << "\n";

    return cout;
}

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


matrix A(1LL * 1, 1LL * 1, 1, 0), C;

int main() {

    in >> n;
    C = A ^ (n - 1);
    out << C.get();

    return 0;
}