#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])
        return false;
    if (diag1[niv-i+n])
        return false;
    if (diag2[niv+i])
        return false;
    return true;*/
    if (col[i]==0 && diag1[niv-i+n]==0 && diag2[niv+i]==0)
        return true;
    return false;
}



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

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