#include <fstream>
#include <iostream>

using namespace std;

const int MOD = 666013;

long long n;

struct matrice{
    long long a, b, c, d;
    // a b
    // c d
};

class matrix{
private:
    matrice mat;
public:

    matrix();
    matrix(long long _11, long long _12, long long _21, long long _22);
    matrix(const matrix &i);

    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) {
   matrix raspuns;

   raspuns.mat.a = ((this -> mat.a * i.mat.a) % MOD  + (this -> mat.b * i.mat.c) % MOD ) % MOD;
   raspuns.mat.b = ((this -> mat.a * i.mat.b) % MOD  + (this -> mat.b * i.mat.d) % MOD ) % MOD;
   raspuns.mat.c = ((this -> mat.c * i.mat.a) % MOD  + (this -> mat.d * i.mat.c) % MOD ) % MOD;
   raspuns.mat.d = ((this -> mat.c * i.mat.b) % MOD  + (this -> mat.d * i.mat.d) % MOD ) % MOD;

   return raspuns;

}

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

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

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

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

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

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

            *this = (*this * *this);
            *this = *this % MOD;
        }
    }
    matrix rez;
    rez = *this * P;
    rez = rez % MOD;
    return rez;
}
matrix :: matrix(const matrix &i) {
    mat.a = i.mat.a;
    mat.b = i.mat.b;
    mat.c = i.mat.c;
    mat.d = i.mat.d;
}

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

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

matrix& matrix::operator=(const matrix &i) {
    mat.a = i.mat.a;
    mat.b = i.mat.b;
    mat.c = i.mat.c;
    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");

int main() {

    matrix A(1, 1, 1, 0);

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

    return 0;
}