#include <fstream>
#include <cstring>
#define Nmax 26
using namespace std;

int N, Solution, V[Nmax], A[Nmax];
bool Line[Nmax], MainDiagonal[Nmax], SecondDiagonal[Nmax];

void Back(int j) {

    for(int i = 1; i <= N; i++) {

        if(Line[i] || MainDiagonal[i + j] || SecondDiagonal[N + i - j])
            continue;

        V[j] = i;
        Line[i] = true;
        MainDiagonal[i + j] = true;
        SecondDiagonal[N + i - j] = true;

        if(j == N) {
            Solution++;
            if(!A[1])
                memcpy(A, V, sizeof(V));
            }
        else
            Back(j + 1);

        Line[i] = false;
        MainDiagonal[i + j] = false;
        SecondDiagonal[N + i - j] = false;

        }

}
void Read() {

    ifstream in("damesah.in");
    in >> N;
    in.close();

}
void Write() {

    ofstream out("damesah.out");
    for(int i = 1; i <= N; i++) out << A[i] << ' ';
    out << '\n' << Solution << '\n';
    out.close();

}
int main() {

    Read();
    Back(1);
    Write();

    return 0;

}