#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,NrSol,C[14],ok1,i,j;
inline void Afisare()
{
    int i,j;
    for(i=0;i<n;i++)
    {
        fout<<C[i]+1<<" ";
    }

}
inline void Plaseaza_Regina(int k)
{
    int i,j,ok;
    if(k==n&&ok1==0) {ok1=1;NrSol++;Afisare();}
    else if(k==n&&ok1==1) NrSol++;
    else
    {
        for(i=0;i<n;i++)
        {
            for(ok=1,j=0;j<k;j++)
            {
                if(C[j]==i||abs(C[j]-i)==(k-j)) ok=0;
            }
            if(ok) {C[k]=i;Plaseaza_Regina(k+1);}
        }
    }
}
int main()
{
    fin>>n;
    Plaseaza_Regina(0);
    fout<<'\n'<<NrSol;
}