#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){
                    if(w==0){
                            ++w;
                    for(int i = 0; i<n; ++i) cout<<v[i]<<' ';
                    cout<<'\n';
                    }
                    else ++w;
            }
            else damesah(k+1);
        }
    }
}

int main()
{
    cin>>n;


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