#include <bits/stdc++.h>
using namespace std;
ifstream fcin("damesah.in");
ofstream fcout("damesah.out");
int n;
int sol_cnt = 0;

bool attacks(int i1, int j1, int i2, int j2) {
    if(i1 == i2) return true;
    if(j1 == j2) return true;
    return abs(i1 - i2) == abs(j1 - j2);
}

bool can_place(int i, int j, vector<pair<int,int>>& placed) {
    for(auto [placed_i, placed_j] : placed)
        if(attacks(i, j, placed_i, placed_j)) return false;
    return true;
}

void back(vector<pair<int,int>>& placed) {
    if((int)placed.size() == n) {
        sol_cnt++;
        if(sol_cnt == 1) {
            for(auto [queen_i, queen_j]: placed)
                fcout << queen_j + 1 << " ";
            fcout << "\n";
        }
        return;
    }
    int i = placed.size();
    for(int j = 0; j < n; j++) {
        if(can_place(i, j, placed)) {
            placed.push_back({i, j});
            back(placed);
            placed.pop_back();
        }
    }
}

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