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

int FirstSolution[151],NumberOfSolutions,v[115],n,pdiag[105],sdiag[105],c[105];
void Read_Number_Of_Pieces();
void Back(int);
void StoresFirstSolution();
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(NumberOfSolutions==0) StoresFirstSolution();
            NumberOfSolutions++;
    }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(!c[i] && !pdiag[i-k+n] && !sdiag[i+k])
                {v[k]=i;
                pdiag[i-k+n]=sdiag[k+i]=c[i]=1;
                Back(k+1);
                pdiag[i-k+n]=sdiag[i+k]=c[i]=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();
}