#include <fstream>
#include <iostream>
using namespace std;
unsigned long long a[6][6],b[6][6],q;
struct el
{
    unsigned long long c[5][5];
};
el v[1000];
void inm( )
{
    int i,j;
    b[1][1]=(a[1][1]*v[q].c[1][1]+a[2][1]*v[q].c[1][2])%666013;
    b[1][2]=(a[1][1]*v[q].c[1][2]+a[1][2]*v[q].c[2][2])%666013;
    b[2][1]=(a[2][1]*v[q].c[1][1]+a[2][2]*v[q].c[2][1])%666013;
    b[2][2]=(a[2][1]*v[q].c[1][2]+a[2][2]*v[q].c[2][2])%666013;

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        a[i][j]=b[i][j];
     cout<<a[1][1]<<" "<<a[1][2]<<'\n'<<a[2][1]<<" "<<a[2][2]<<'\n'<<'\n';

    q-=1;
   // return 0;
}

int lgput(int p)
{
    int i,j;
    if(p==0) return 1;
    else
    {
        cout<<a[1][1]<<" "<<a[1][2]<<'\n'<<a[2][1]<<" "<<a[2][2]<<'\n'<<'\n';
        if(p%2==0)
        {

            b[1][1]=(a[1][1]*a[1][1]+a[1][2]*a[2][1])%666013;
            b[1][2]=(a[1][1]*a[1][2]+a[1][2]*a[2][2])%666013;
            b[2][1]=(a[2][1]*a[1][1]+a[2][2]*a[2][1])%666013;
            b[2][2]=(a[2][1]*a[1][2]+a[2][2]*a[2][2])%666013;


            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    a[i][j]=b[i][j];
            return lgput(p/2);
        }
        else
        {
            q+=1;
            v[q].c[1][1]=a[1][1];
            v[q].c[1][2]=a[1][2];
            v[q].c[2][1]=a[2][1];
            v[q].c[2][2]=a[2][2];
            b[1][1]=(a[1][1]*a[1][1]+a[1][2]*a[2][1])%666013;
            b[1][2]=(a[1][1]*a[1][2]+a[1][2]*a[2][2])%666013;
            b[2][1]=(a[2][1]*a[1][1]+a[2][2]*a[2][1])%666013;
            b[2][2]=(a[2][1]*a[1][2]+a[2][2]*a[2][2])%666013;

            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    a[i][j]=b[i][j];
            return lgput((p-1)/2);
        }
    }
}



int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int n,i,j,e;
    f>>n;
    a[1][1]=1;
    a[2][1]=1;
    a[1][2]=1;
    a[2][2]=0;
    b[1][1]=1;
    b[2][1]=1;
    b[1][2]=1;
    b[2][2]=0;
   /* if(e>=3)
    {
        e=lgput(n-1);
        g<<a[1][1];
    }
    if(e==0)
        g<<"0";
    if(e==1)
        g<<"1";
    if(e==2)
        g<<"1";
    if(e==3)
        g<<"2";*/
    if(n>=4)
    {
        e=lgput(n-4);
        while(q!=0)
            inm();
        //cout<<e;
        g<<a[1][2];
    }
    if(n==0)
        g<<"0";
    if(n==1)
        g<<"1";
    if(n==2)
        g<<"1";
    if(n==3)
        g<<"2";

    f.close();
    g.close();
    return 0;
}