#include <bits/stdc++.h>
using namespace std;
ifstream fcin("damesah.in");
ofstream fcout("damesah.out");
int n, sol_cnt = 0;
bool col_used[15], diag1[30], diag2[30];
// diag1: i-j constant, diag2: i+j constant

bool can_place(int i, int j) {
    return !col_used[j] && !diag1[i - j + n] && !diag2[i + j];
}

void back(vector<pair<int,int>>& placed) {
    if((int)placed.size() == n) {
        sol_cnt++;
        if(sol_cnt == 1) {
            for(auto [qi, qj]: placed) fcout << qj + 1 << " ";
            fcout << "\n";
        }
        return;
    }
    int i = placed.size();
    for(int j = 0; j < n; j++) {
        if(can_place(i, j)) {
            col_used[j] = diag1[i - j + n] = diag2[i + j] = true;
            placed.push_back({i, j});
            back(placed);
            placed.pop_back();
            col_used[j] = diag1[i - j + n] = diag2[i + j] = false;
        }
    }
}

int main() {
    fcin >> n;
    vector<pair<int,int>> placed;
    back(placed);
    fcout << sol_cnt << "\n";
    return 0;
}