#include<fstream>
#define N 14
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
int v[N], viz[N], n, count, primul=1;
ofstream g("damesah.out");
void afis()
{
    for(int i=1; i<=n; i++)
        g<<v[i]<<" ";
}
int se_ataca(int k, int poz)
{
    for(int i=1; i<k; i++)
        if((k-i)==abs(v[i]-poz))return 1;
    return 0;
}
void back(int k)
{
    if(k==n+1)
    {
        count++;
        if(primul)
        {
            afis();
            primul = 0;
        }
    }
    for(int i=1; i<=n; i++)
        if(!viz[i] && !se_ataca(k,i))
        {
            viz[i]=1;
            v[k]=i;
            back(k+1);
            viz[i]=0;
        }
}
int main()/*v[i]=coloana pe care se afla dama de pe linia i*/
{
    ifstream f("damesah.in");
    f>>n;
    back(1);
    g<<"\n"<<count;
    f.close();
    return 0;
}