//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);

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)){
                C[level+1][i]=C[level+1][i-1]=C[level+1][i+1]=1;
                Generate(level+1);
            }
        }
    }
}

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