#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Dame {
    int N, nsol = 0;
    vector<char> ln, dp, ds;
    vector<char> solutie;
    explicit Dame(char N) {
        this->N = N;
        ln.resize(N);
        dp.resize(2*N);
        ds.resize(2*N);
    }
    void generare(ostream &out) {
        if(solutie.size() < N) {
            int j = solutie.size();
            for(int i=0; i<N; ++i) {
                if(!ln[i] && !ds[i+j] && !dp[i-j+N-1]) {
                    solutie.push_back(i);
                    ln[i] = 1;
                    ds[i+j] = 1;
                    dp[i-j+N-1] = 1;
                    generare(out);
                    ln[i] = 0;
                    ds[i+j] = 0;
                    dp[i-j+N-1] = 0;
                    solutie.pop_back();
                }
            }
        } else {
            if(!nsol) {
                for(auto a: solutie) {
                    out << (int)a + 1 << ' ';
                }
                out << '\n';
            }
            ++nsol;
        }
    }
};

int main() {
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    int N;
    fin >> N;
    Dame generator(N);
    generator.generare(fout);
    fout << generator.nsol << '\n';
    return 0;
}