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

int D[20],n,first=0,ct=0;
int C[20][20];

void Generate(int);
bool IsOk(int,int);
void Print(int);
void Set(int[][20],int,int,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(IsOk(level,i)){
                Set(C,level,i,1);
                Generate(level+1);
                Set(C,level,i,0);
            }
        }
    }
}

bool IsOk(int level,int coloana){
    if(C[level][coloana]==0) return true;
    else return false;
}
void Print(int n){
    for(int i=1;i<=n;i++){
        cout<<D[i]<<" ";
    }
}

void Set(int C[][20],int level,int i,int x){
    for(int t=level+1;t<=n;t++) C[t][i]=x;
    for(int t=1;(level+t<=n)&&(i+t<=n);t++) C[level+t][i+t]=x;
    for(int t=1;(level+t<=n)&&(i-t)>=1;t++) C[level+t][i-t]=x;
}