#include <bits/stdc++.h>

#define NMax 40

using namespace std;

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

int N,nrSol,Queen[NMax];
bool col[NMax],diagP[NMax],diagS[NMax];

void Back(int k)
{
    if(k==N+1)
    {
        if(nrSol<1)
            for(int i=1;i<=N;i++)
                fout<<Queen[i]<<" ";
        nrSol++;
    }
    for(int i=1;i<=N;i++)
        if(col[i]==false && diagP[i+k]==false && diagS[i+N-1-k]==false)
        {
            Queen[k]=i;
            col[i]=diagP[i+k]=diagS[i+N-1-k]=true;
            Back(k+1);
            col[i]=diagP[i+k]=diagS[i+N-1-k]=false;
        }
}

int main()
{
    fin>>N;
    Back(1);
    fout<<"\n"<<nrSol;

    return 0;
}