#include <iostream>
#include <fstream>
using namespace std;

int FirstSolution[15],NumberOfSolutions,v[15],n;
void Read_Number_Of_Pieces();
void Back(int);
void StoresFirstSolution();
bool Valid();
void Write_Number_Of_Pieces_And_First_Solution();

int main()
{

    Read_Number_Of_Pieces();
    Back(1);
    Write_Number_Of_Pieces_And_First_Solution();

    return 0;
}
void Write_Number_Of_Pieces_And_First_Solution()
{
    ofstream g("damesah.out");
    for(int i=1;i<=n;i++) g<<FirstSolution[i]<<" ";

    g<<"\n"<<NumberOfSolutions;
}
void Back(int k)
{
    if(k>n)
    {
        if(Valid())
        {
            if(NumberOfSolutions==0) StoresFirstSolution();
            NumberOfSolutions++;
        }
    }
        else
        {
            for(int i=1;i<=n;i++)
            {
                v[k]=i;
                Back(k+1);
                v[k]=0;
            }
        }


}
void StoresFirstSolution()
{
    for(int i=1;i<=n;i++)
    {
        FirstSolution[i]=v[i];
    }
}

void Read_Number_Of_Pieces()
{
    ifstream f("damesah.in");
    f>>n;
    f.close();
}
bool Valid()
{

    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(v[i]==v[j]) return false;
        }
    }
    for(int i=1;i<n;i++)
    {if(v[i]==v[i+1]-1) return false;
            if(v[i]==v[i+1]+1) return false;
    }
    return true;
}