#include <fstream>
using namespace std;
ifstream fi ("damesah.in");
ofstream fo ("damesah.out");
int col[30],diag1[30],diag2[30],n,nr,A[30];
void Backtrack(int k)
{
    for(int i=1; i<=n; i++)
    {
        if(col[i]!=1 and diag1[i+k]!=1 and diag2[i-k+n+1]!=1)
        {
            A[k]=i;
            col[i]=1;
            diag1[i+k]=1;
            diag2[i-k+n+1]=1;
            if(k==n)
            {
                nr++;
                if(nr==1)
                {
                    for(int j=1; j<=n; j++)
                        fo<<A[j]<<" ";
                }
            }
            else Backtrack(k+1);
            col[i]=0;
            diag1[i+k]=0;
            diag2[i-k+n+1]=0;
        }
    }
}
int main()
{
    fi>>n;
    Backtrack(1);
    fo<<"\n";
    fo<<nr;
    return 0;
}