#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N, A[18], counter = 0;

void print_sol(int n){
    for(int i = 1; i <= n; i++){
        fout << A[i] << " ";
    }
    fout << "\n";
}

int abs(int a){
    if(a >= 0) return a; else return -a;
}

bool place(int pos){
    for(int i = 1; i < pos; i++){
        if((A[i] == A[pos]) || abs(A[i] - A[pos]) == abs(i - pos))
            return 0;
    }
    return 1;
}

void queen (int N){
    int k = 1;
    while(k!=0){
        do {
            A[k]++;
        } while ( (A[k] <= N) && !place(k));
        if(A[k] <= N){
            if(k == N ) {
                counter++;
                if(counter == 1){
                    print_sol(N);
                }
            }
            else {
                k++;
                A[k] = 0;
            }
        } else {
            k--;
        }
    }
    fout << counter;
}

int main()
{
    fin >> N;
    queen(N);
}