#include <bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n, viz[14], sol[14], ct, sol_min[14], gasit;
int diagpr[30], diagsec[30];


bool Valid(int l, int c)
{
    if(viz[c] == 0 && diagpr[n - c + l] == 0 && diagsec[l + c - 1] == 0)
        return 1;
    else return 0;
}

void SolutieMinima()
{
    for(int i=1; i<=n; i++)
        sol_min[i] = sol[i];
}

void Back(int k)
{
    for(int i=1; i <= n; i++)
        if(Valid(k, i))
        {
            viz[i] = 1;
            diagpr[n - i + k] = 1;
            diagsec[k + i - 1] = 1;
            sol[k] = i;
            if(k==n)
                {
                    if(gasit==0)
                        SolutieMinima(), gasit=1, ct=1;
                    else ct++;
                }
            else Back(k+1);
            viz[i] = 0;
            diagpr[n - i + k] = 0;
            diagsec[k + i -1] = 0;
            sol[k] = 0;
        }
}

int main()
{
    fin >> n;
    Back(1);
    for(int i=1; i<=n; i++)
        fout << sol_min[i] << " ";
    fout << "\n";
    fout << ct;
    return 0;
}