#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++)
            {
                if(v[k-1]!=i && v[k-1]+1!=i && v[k-1]-1!=i)
                {v[k]=i;
                Back(k+1);
                }
                v[k]=0;
            }
        }


}
bool Valid()
{
    int k;
    for(int i=1;i<=n;i++)
    {
        k=0;
        for(int j=i+1;j<=n;j++)
        {
            k++;
            if(v[i]==v[j]) return 0;
            if(v[j]-k==v[i] || v[j]+k==v[i]) return 0;
        }
    }

    return 1;
}
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();
}