#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int col[20], diag1[20], diag2[20];
int st[20],n,nr;
bool prima=true;


bool valid (int niv)
{
    int i = st[niv];
    if (col[i]==0 && diag1[niv-i+n]==0 && diag2[niv+i]==0)
    {
        col[i]=1;
        diag1[niv-i+n]=1;
        diag2[niv+i]=1;
        return true;
    }
    else return false;
}



void printSol()
{
    for (int i=1;i<=n;i++)
        fout<<st[i]<<" ";
}

void backtrack(int niv)
{
    for (int i=1;i<=n;i++)
    {
        st[niv]=i;
        if (valid(niv))
        {
            if (niv==n)
            {
                nr++;
                if (prima)
                {
                    prima = false;
                    printSol();
                }
            }
            else
                backtrack(niv+1);
            col[i]=0;
            diag1[niv-i+n]=0;
            diag2[niv+i]=0;
        }
    }
}

int main()
{
    fin>>n;
    backtrack(1);
    fout<<"\n"<<nr<<"\n";
    return 0;
}