#include <fstream>
#include <vector>

using namespace std;

int N;
long long solutii = 0;
vector<int> dame;
vector<int> prima_solutie;
bool col[30], d1[30], d2[30];

void back(int linie) {
    if (linie == N) {
        if (solutii == 0) prima_solutie = dame;
        solutii++;
        return;
    }

    for (int c = 0; c < N; ++c) {
        if (!col[c] && !d1[linie + c] && !d2[linie - c + N]) {
            dame[linie] = c + 1;
            col[c] = d1[linie + c] = d2[linie - c + N] = true;
            
            back(linie + 1);
            
            col[c] = d1[linie + c] = d2[linie - c + N] = false;
        }
    }
}

int main() {
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    
    fin >> N;
    dame.resize(N);
    
    back(0);
    
    for (int i = 0; i < N; ++i) fout << prima_solutie[i] << (i == N - 1 ? "" : " ");
    fout << "\n" << solutii << "\n";
    
    fin.close();
    fout.close();
    return 0;
}