#include <iostream>
#include <fstream>
#include <cstdlib>
// #define mod 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
unsigned long long stMatrix[3][3], ndMatrix[3][3], mod = 666013, i, j;
void multiply(unsigned long long A[3][3], unsigned long long B[3][3])
{
    // for (i = 1; i <= 2; i++)
    // {
    //     for (j = 1; j <= 2; j++)
    //     {
    //         cout << A[i][j] << " ";
    //     }
    //     cout << '\n';
    // }
    unsigned long long temp[3][3] = {0};
    temp[1][1] = (A[1][1] * B[1][1]) + (A[1][2] * B[2][1]);
    temp[1][2] = (A[1][1] * B[1][2]) + (A[1][2] * B[2][2]);
    temp[2][1] = (A[2][1] * B[1][1]) + (A[2][2] * B[2][1]);
    temp[2][2] = (A[2][1] * B[1][2]) + (A[2][2] * B[2][2]);
    for (i = 1; i <= 2; i++)
    {
        for (j = 1; j <= 2; j++)
        {
            cout << temp[i][j] % mod << " ";
            A[i][j] = temp[i][j] % mod;
        }
        cout << endl;
    }
    cout << endl;
}

void matrix_pow(unsigned long long power)
{
    while (power > 0)
    {
        // cout << "ok" << power;
        if (power % 2 == 1)
        {
            multiply(stMatrix, ndMatrix);
        }
        multiply(ndMatrix, ndMatrix);
        power /= 2;
    }
}

int main()
{
    stMatrix[1][1] = 0;
    stMatrix[1][2] = 1; // stMatrix
    stMatrix[2][1] = 1;
    stMatrix[2][2] = 1;
    ndMatrix[1][1] = 0;
    ndMatrix[1][2] = 1; // ndMatrix
    ndMatrix[2][1] = 1;
    ndMatrix[2][2] = 1;

    unsigned long long n;
    fin >> n;

    if (n == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    matrix_pow(n);
    cout << stMatrix[1][1] << " " << stMatrix[1][2] << "\n"
         << stMatrix[2][1] << " " << stMatrix[2][2] << "\n"; // Compute matrix^n
    unsigned long long fib_n = stMatrix[1][1] % mod;         // Fₙ = matrix[0][1] after exponentiation

    fout << fib_n << endl;

    return 0;
}