#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>

using namespace std;

int N;
int countAns;
vector<int> sol;

void go(int i, int cols, int diagsW, int diagsB, vector<int>& mat) {
    if (i >= N) {
        ++countAns;
        if (sol.empty()) {
            for (int x : mat)
                sol.push_back(x);
        }
        return;
    }
    
    for (int j = 0; j < N; j++) {
        if ((1 << j) & cols)
            continue;
        if ((1 << (N + i - j)) & diagsW)
            continue;
        if ((1 << (i + j)) & diagsB)
            continue;
        
        if (sol.empty())
            mat.push_back(j);
        
        go(i + 1, cols | (1 << j), (1 << (N + i - j)) | diagsW, (1 << (i + j)) | diagsB, mat);
        if (sol.empty() && !mat.empty())
            mat.pop_back();
    }       
}

int main() {
    ifstream f("damesah.in");
    ofstream g("damesah.out");
    
    f >> N;

    vector<int> lines;
    go(0, 0, 0, 0, lines);

    for (int x : sol)
        g << x + 1 << ' ';
    g << '\n' << countAns << '\n';


    f.close();
    g.close();
    return 0;
}