#include<fstream>
#define N 14
#define abs(x) ((x)>0?(x):(-(x)))
using namespace std;
int v[N],lin[N], col[N], diag1[2*N],diag2[2*N], n, count, primul=1;
ofstream g("damesah.out");
inline void afis()
{
    for(int i=1; i<=n; i++)
        g<<v[i]<<" ";
}
void back(int k)
{
    if(k==n+1)
    {
        count++;
        if(primul)
        {
            afis();
            primul = 0;
        }
    }
    for(int i=1; i<=n; i++)
    /*verific daca am liniile, coloenele si diagonalele ocupate*/
        if(!lin[k] && !col[i] && !diag1[N+i-k] && !diag2[k+i])
        {
            lin[k]=1;
            col[i]=1;
            diag1[N+i-k]=1;
            diag2[k+i]=1;
            v[k]=i;
            back(k+1);
            lin[k]=0;
            col[i]=0;
            diag1[N+i-k]=0;
            diag2[k+i]=0;
        }
}
int main()/*v[k]=coloana pe care se afla dama de pe linia k*/
{
    ifstream f("damesah.in");
    f>>n;
    back(1);
    g<<"\n"<<count;
    f.close();
    return 0;
}