#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 30 + 5;

int N,nrSol;
bool ans;
bool col[NMax],diagPrin[2*NMax],diagSec[2*NMax];
int queen[NMax];

void backT(int);

int main() {
    in>>N;

    backT(1);
    out<<'\n'<<nrSol<<'\n';

    in.close();out.close();
    return 0;
}

void backT(int nr) {
    if (nr == N + 1) {
        if (!ans) {
            ans = true;

            for (int i=1;i < nr;++i) {
                out<<queen[i]<<' ';
            }
        }

        ++nrSol;
        return;
    }

    for (int j=1;j <= N;++j) {
        if (!diagPrin[nr-j+NMax] && !diagSec[nr+j] && !col[j]) {

            diagPrin[nr-j+NMax] = 1;
            diagSec[nr+j] = 1;
            col[j] = 1;

            queen[nr] = j;
            backT(nr+1);

            diagPrin[nr-j+NMax] = 0;
            diagSec[nr+j] = 0;
            col[j] = 0;
        }
    }
}