#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");

    int n; cin >> n;
    int n_solutions = 0;
    bool queen_on_diagonal[30] = {0};
    bool queen_on_antidiagonal[30] = {0};
    bool queen_on_column[15] = {0};

    int queens_columns[15] = {0};
    int i = 1;
    while (i) {
        queens_columns[i]++;
        if (i > n) {
            n_solutions++;
            if (n_solutions == 1) {
                for (int j = 1; j <= n; ++j)
                    cout << queens_columns[j] << " ";
                cout << endl;
            }
            --i;
        } else if (queens_columns[i] <= n) {
            int row = i;
            int column = queens_columns[i];
            int diagonal = n - column + row;
            int antidiagonal = row + column - 1;
            if (!queen_on_diagonal[diagonal] 
                and !queen_on_antidiagonal[antidiagonal]
                and !queen_on_column[column]) {
                queen_on_diagonal[diagonal] = true;
                queen_on_column[column] = true;
                queen_on_antidiagonal[antidiagonal] = true;
                ++i;
            }
        } else {
            queens_columns[i] = 0;
            --i;

            int row = i;
            int column = queens_columns[i];
            int diagonal = n - column + row;
            int antidiagonal = row + column - 1;
            queen_on_diagonal[diagonal] = false;
            queen_on_antidiagonal[antidiagonal] = false;
            queen_on_column[column] = false;
        }
    }
    
    cout << n_solutions << endl;

    return 0;
}