#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int total,n;
int st[20],fol[20];

int valid(int k){
    for(int i = 1; i < k; i++){
        if(st[k] + k == st[i] + i ||
           st[k] - k == st[i] - i){
            return 0;
           }
    }
    return 1;
}
void afisare(){
    if(total == 0){
        for(int i = 1; i <= n; i++){
            g << st[i] <<" ";
        }
        g <<"\n";
    }
    total++;
}
void back(int k){
    for(int i = 1; i <= n; i++){
        if(fol[i] == 0){
            fol[i] = 1;
            st[k] = i;

            if(valid(k)){
                if(k == n)
                    afisare();
                else
                    back(k + 1);
            }
            fol[i] = 0;
        }
    }
}
int main()
{
    f >> n;
    back(1);
    g << total;
    return 0;
}