#include <iostream>
#include <math.h>
#include<fstream>
#include <stdlib.h>

using namespace std;
int N, Count, k;
bool ok, print = true;
int x[13];

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

inline void printSol()
{
    for(int i = 1; i <= N; i++)
        g << x[i] << " ";
    g << "\n";
}
inline bool valid(int k){
    for (int i = 1; i < k; i++)
        if ((x[k] == x[i]) || (k - i == abs(x[k] - x[i]))){
            return false;
    }
    return true;
}

void backTraking(int n){
    int ok, k;
    k = 1;
    x[k] = 0;
    while (k > 0) {
        ok = 0;
        while ((x[k] < n) && (!ok)) {
            x[k]++;
            ok = valid(k);
        }
        if (!ok){
            k--;
        }
        else{
            if (k == n) {
                if (print)
                {
                    printSol();
                    print = false;
                }
                Count++;
            }
            else {
                k++;
                x[k] = 0;
            }
        }
    }
}

int main()
{
    f >> N;
    backTraking(N);
    g << Count << "\n";
}