#include <bits/stdc++.h>

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

void mark(int i, int j, int m[15][15], int n) {
    for (int aux_i = i; aux_i < n; aux_i++) {
        m[aux_i][j]++;
    }
    for (int aux_j = j; aux_j < n; aux_j++) {
        m[i][aux_j]++;
    }
    for (int k = 1; k + i < n && j - k >= 0; k++) {
        m[k + i][j - k]++;
    }
    for (int k = 1; k + i < n && j + k < n; k++) {
        m[k + i][j + k]++;
    }
}

void unmark(int i, int j, int m[15][15], int n) {
    for (int aux_i = i; aux_i < n; aux_i++) {
        m[aux_i][j]--;
    }
    for (int aux_j = j; aux_j < n; aux_j++) {
        m[i][aux_j]--;
    }
    for (int k = 1; k + i < n && j - k >= 0; k++) {
        m[k + i][j - k]--;
    }
    for (int k = 1; k + i < n && j + k < n; k++) {
        m[k + i][j + k]--;
    }
}
int cnt;
vector<vector<int>>sol;

void back(int n, int line, vector<int>ans, int possible[15][15]) {
    if (line == n) {
        sol.push_back(ans);
        cnt++;
        return;
    }

    for (int i = 0 ; i < n; i++) {
        if (possible[line][i] == 0) {
            ans.push_back(i);
            possible[line][i]++;
            mark(line, i, possible, n);
            back(n, line + 1, ans, possible);
            unmark(line, i, possible, n);
            possible[line][i]--;
            ans.pop_back();
        }

    }

}

int main() 
{
    int n, possible[15][15];
    fin>>n;
    vector<int>ans;
    memset(possible, 0, sizeof(possible));
    back(n, 0, ans, possible);
        for (int j = 0; j < n; j++) {
            fout<<sol[0][j] + 1<< " ";
        }
        fout<<endl;
    fout<<cnt;

    return 0;
}