#include <fstream>
#include <vector>
#define vi vector<int>
#define vvi vector<vector<int>>
#define NMAX 30
using namespace std;


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

int n, cnt;
vi line(NMAX, 1);
vi column(NMAX, 1);
vi diag(NMAX, 1);
vi diag_sec(NMAX, 1);
vi solution;

bool check_free(int x, int y) {
    return line[x] && column[y] && diag[x - y + n] && diag_sec[x + y];
}

void backt(vi solution, int k) {
    if (k == n + 1) {
        if (cnt == 0) {
            for (int i = 1; i <= n; i++) {
                g << solution[i - 1] << ' ';
            }
        }
        cnt++;
    }

    for (int i = 1; i <= n; i++) {
        if (check_free(k, i)) {
            line[k] = 0;
            column[i] = 0;
            diag[k - i + n] = 0;
            diag_sec[i + k] = 0;

            solution.push_back(i);
            backt(solution, k + 1);

            line[k] = 1;
            column[i] = 1;
            diag[k - i + n] = 1;
            diag_sec[i + k] = 1;

            solution.pop_back();
        }
    }
}


int main() {
    f >> n;

    backt(solution, 1);

    g << "\n" << cnt;

    return 0;
}