//Infoarena. Arhiva Educationala. Problema Damelor.
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;

int D[20],n,first=0,ct=0;
int col[20],left_diagonal[40],right_diagonal[40];

void Generate(int);
void Print(int);

int main(){
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    cin>>n;

    Generate(1);
    cout<<"\n"<<ct;

}

void Generate(int level){
    if(level==n+1){
        ct++;
        if(first==0){
            Print(n);
            first=1;
        }
    }else{
        for(int i=1;i<=n;i++){
            D[level]=i;
            if(col[i]==0 && left_diagonal[level+i]==0 && right_diagonal[level+n-i]==0){
                col[i]=left_diagonal[level+i]=right_diagonal[level+n-i]=1;
                Generate(level+1);
                col[i]=left_diagonal[level+i]=right_diagonal[level+n-i]=0;
            }
        }
    }
}


void Print(int n){
    for(int i=1;i<=n;i++){
        cout<<D[i]<<" ";
    }
}