#include <bits/stdc++.h>;
using namespace std;

ifstream f("12perm.in");
ofstream g("12perm.out");

int n,nr,s[15000005];

void afisare()
{
   for(int i=1;i<=n;i++)
        g<<s[i]<<' ';
   g<<'\n';
}

bool ok( int k)
{
    if(k>1 && abs(s[k]-s[k-1])>=3 ) return 0;
    for(int i=1;i<k;i++)
        if(s[i]==s[k]) return 0;
    return 1;
}

int generare(int k)
{
    for( int i = 1 ; i <= n ; ++i)
    {
        s[k]=i;
        if(ok(k))
            if(k<n) generare(k+1);
            else
                {
                    afisare();
                    nr++;
                    nr = nr % 1048576;
                }
    }
}

int main()
{
    f>>n;
    generare(1);
    g<<nr;
}