#include <iostream>
#include <fstream>
#define N 20
#define in "damesah.in"
#define out "damesah.out"

using namespace std;

ifstream fin(in);
ofstream fout(out);

int n;
bool col[N],dp[N],ds[N];
int Rand[N];
int ct=0;
//Daca se afla deja o regina pe coloana i, sau una din cele doua diagonale(principala secundara)
//se sare elementul
//in vectorul Rand[] se memoreaza coloana reginei plasata pe randul respectiv

bool gasit=false;

void BK(int i) //pentru fiecare rand
{
    if(i==n+1)
    {
        ++ct;
        if(!gasit)
        {
            for(int i=1; i<=n; ++i)
                for(int j=1; j<=n; ++j)
                    if(Rand[i]==j) fout<<j<<" ";
            gasit=true;
        }
    }
    else
    {
        for(int j=1; j<=n; ++j)
            if(!col[j] && !dp[n+(j-i)] && !ds[(i+j)-1]) //daca nu se ataca cu celelalte regine
            {
                Rand[i]=j;
                col[j]=true;
                dp[n+(j-i)]=true;
                ds[(i+j)-1]=true;
                   BK(i+1);
                col[j]=false;
                dp[n+(j-i)]=false;
                ds[(i+j)-1]=false;
            }
    }
}

int main()
{
    fin>>n;
    BK(1);

    fout<<"\n"<<ct<<"\n";

    fin.close(); fout.close();
    return 0;
}