#include <fstream>

constexpr int kMaxSize = 13;

std::ifstream input("damesah.in");
std::ofstream output("damesah.out");

int counter;
int table_size;
int position[kMaxSize];

void backtracking(int pos)
{
    if (pos == table_size) {
        ++counter;
        if (counter == 1) {
            for (int i = 0; i < table_size; ++i) output << position[i] + 1 << ' ';
            output << '\n';
        }
    }
    for (int i = 0; i < table_size; ++i) {
        bool valid = true;
        for (int j = 0; j < pos; ++j) {
            if (position[j] == i ||
                (position[j] - j == i - pos) ||
                (position[j] + j == i + pos)) {
                  valid = false;
                  break;
            }
        }
        if (valid) {
            position[pos] = i;
            backtracking(pos + 1);
        }
    }
}

int main()
{
    int n;

    input >> n;
    table_size = n;
    backtracking(0);

    output << counter << '\n';
    return 0;
}