#include <bits/stdc++.h>

#define N_MAX 40

using namespace std;
ifstream fin("damesah.in");

ofstream fout("damesah.out");
bool col_curenta[N_MAX], diag_princp[N_MAX], diag_sec[N_MAX];

int salvare[N_MAX];
int rez;
int n;
void solve(int linie)
{
    if (linie == n)
    {
        rez++;
        if (rez == 1)
            for (int i = 0; i <n; i++)
                fout << salvare[i] << ' ';
    }
    else
    {
        for (int col = 0; col < n; col++)
        {
            if (!col_curenta[col] && !diag_princp[col- linie + n - 1] && !diag_sec[linie + col])
            {
                salvare[linie] = col + 1;
                col_curenta[col] = diag_princp[col- linie + n - 1] = diag_sec[linie + col] = true;
                solve(linie + 1);
                col_curenta[col] = diag_princp[col -linie+ n - 1] = diag_sec[linie + col] = false;
            }
        }
    }
}
int main()
{
    fin >> n;
    solve(0);
    fout << '\n';
    fout << rez;
}