#include <iostream>
#include<fstream>
#define N 15
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n;
int x[N];//x[i]=j pe linia i dama se afla pe col j
int diag1[2*N];//principala dif este constanta
int diag2[2*N];//sec suma este constanta
bool viz[N];

int ct;

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

void backt(int k)
{
    int i;
    for(i=1;i<=n;++i)
        if(!viz[i])//inca nu a fost pe col resp
        if(diag1[n-(k-i)]==0&&diag2[2*n-k-i+1]==0)
    {
        viz[i]=1;
        x[k]=i;
        diag1[n-(k-i)]=1;
        diag2[2*n-k-i+1]=1;
        if(k<n)backt(k+1);
        else {
                if(ct==0)print();
                ct++;
            }
        viz[i]=0;
        diag1[n-(k-i)]=0;
        diag2[2*n-k-i+1]=0;

    }
}

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