#include <iostream>
#include <fstream>
#define ll long long
#define MOD 666013

using namespace std;

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

//dp[i] = dp[i-1] * A + dp[i-2] * B + dp[i-3] * C
int m[2][2]={{0,1},{1,1}};
int fib[2][2]={{0,1},{0,0}};
ll n;
int sol[2][2]={{1,0},{0,1}};

void MatrixMultiply(int x[2][2],int y[2][2])
{
    ll rez[2][2]={0};
    for(int i=0; i < 2 ;i++)
        for(int j=0; j < 2;j++)
            for(int k=0 ; k<2 ;k++)
                rez[i][j]=(rez[i][j]+ (1LL * x[i][k] * y[k][j])%MOD)%MOD;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            x[i][j]=rez[i][j];

}

void pow(int rez[2][2],int p)
{
    while(p)
    {
        if(p%2)
            MatrixMultiply(rez,m);
        MatrixMultiply(m,m);
        p/=2;
    }
}

int main()
{
    fin>>n;
    pow(sol,n-1);
    MatrixMultiply(fib,sol);
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
            cout<<sol[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
            cout<<fib[i][j]<<" ";
        cout<<endl;
    }
    fout<<fib[0][1];
    return 0;
}