#include <fstream>
#include<cmath>
using namespace std;

ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n, v[15], w = 0;

bool valid(int k){
    for(int i = 0; i < k; ++i){
            if(v[i]==v[k]) return false;
            if(abs(v[i] - v[k])== abs(i - k)) return false;
    }
    return true;
}


void damesah(int k){
    for(int i = 1; i<=n; ++i){
        v[k] = i;
        if(valid(k)){
            if(k==n-1) ++w;
            else damesah(k+1);
        }
    }
}


void damesah0(int k){
    for(int i = 1; i<=n; ++i){
        v[k] = i;
        if(valid(k)){
            if(k==n-1){
                    ++w;
                    for(int i = 0; i<n; ++i) cout<<v[i]<<' ';
                    cout<<'\n';

            }
            else{ if(w==0) damesah0(k+1);
                else(damesah(k+1));
            }
        }
    }
}


int main()
{
    cin>>n;


    damesah0(0);
    cout<<w;
    return 0;
}