#include <bits/stdc++.h>
#define mod 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct Matrix
{
    int a[5][5];
    int n,m;
};
Matrix A,U,I;
void Initializare()
{
    U.n=U.m=I.n=I.m=2;
    U.a[0][1]=U.a[1][0]=U.a[1][1]=1;
    I.a[0][0]=I.a[1][1]=1;
    A.n=1;
    A.m=2;
    A.a[0][0]=A.a[0][1]=1;
}


Matrix MatrixProduct(Matrix A,Matrix B)
{
    Matrix R;
    R.n=A.n;
    R.m=B.m;
    for(int i=0;i<R.n;i++)
        for(int j=0;j<R.m;j++)
        {
            R.a[i][j]=0;
            for(int k=0;k<A.m;k++)
                R.a[i][j]+=(1LL*A.a[i][k]*B.a[k][j])%mod;
        }
    return R;
}
Matrix PutLog(Matrix X, int n)
{
    Matrix P=I;
    while (n)
    {
        if (n & 1)
        {
            P=MatrixProduct(P,X);
            n--;
        }
        X = MatrixProduct(X,X);
        n >>= 1;
    }
    return P;
}

int main()
{
    int n;
    Initializare();
    cin>>n;
    U=PutLog(U,n-2);
    A=MatrixProduct(A,U);
    cout<<A.a[0][1]<<"\n";
    cout<<U.a[0][0]<<" "<<U.a[0][1]<<"\n";
    cout<<U.a[1][0]<<" "<<U.a[1][1]<<"\n";



    return 0;
}
/// 1 1 2 3 5 8 13