#include<fstream>
using namespace std;
fstream fin,fout;
int col[15],lin[15],diag1[30],diag2[30],n,j,nr,regina[15],regina1[15];
void dame(int l, int n)
{
    int c;
    if (l==n)
    {
        if (nr<1)
        {
            for (c=0;c<n;c++)
            {
                regina1[c]=regina[c]+1;
            }
        }
        nr++;
    }
    else
        {
            for (c=0;c<n;c++)
            {
                if (col[c]!=1 && diag1[c-l+n-1]!=1 && diag2[l+c]!=1)
                {
                        regina[l]=c;

                    col[c]=1;
                    diag1[c-l+n-1]=1;
                    diag2[l+c]=1;
                    dame(l+1,n);
                    col[c]=0;
                    diag1[c-l+n-1]=0;
                    diag2[l+c]=0;
            }
        }
    }
}
int main()
{
     ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    fin>>n;
    int i;
    dame(0,n);
    for(i=0;i<n;i++) fout<<regina1[i]<<" ";
    fout<<'\n';
    fout<<nr;
    return 0;
}