#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int queens[14], col[14], main_diag[28], second_diag[28], n, cnt;

int BKT(int row){
    if (row == n + 1){
        if (cnt == 0)
            for (int i = 1; i <= n; i++)
                fout << queens[i] << ' ';
        cnt++;
    }else{
        for (int c = 1; c <= n; c++)
            if (!col[c] && !main_diag[c-row + n] && !second_diag[c + row - 1]){
                queens[row] = c;
                col[c] = main_diag[c - row + n] = second_diag[c + row - 1] = 1;
                BKT(row + 1);
                col[c] = main_diag[c - row + n] = second_diag[c + row - 1] = 0;
            }
    }
}

int main()
{
    fin >> n;
    BKT(1);
    fout << '\n' << cnt;
    return 0;
}