#include <bits/stdc++.h>
#define MAX 13

using namespace std;

int n, sol[MAX + 1], aux[MAX + 1], colVf[MAX + 1];
int diagPrinVf[2 * MAX + 2], diagSecVf[2 * MAX + 2];
bool solutieE;
int cnt;

void bkt(int k)
{
    if(k == n + 1)
    {
        if(!solutieE)
        {
            solutieE = 1;

            for(int i = 1; i <= n; i++)
                sol[i] = aux[i];
        }

        cnt++;
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!colVf[i] && !diagPrinVf[k + i - 1] && !diagSecVf[k + n - i])
        {
            colVf[i] = 1;
            diagPrinVf[k + i - 1] = 1;
            diagSecVf[k + n - i] = 1;
            aux[k] = i;
            bkt(k + 1);
            colVf[i] = 0;
            diagPrinVf[k + i - 1] = 0;
            diagSecVf[k + n - i] = 0;
        }
    }
}

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

    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    srand(time(NULL));

    fin >> n;

    bkt(1);

    for(int i = 1; i <= n; i++)
        fout << sol[i] << " ";

    fout << '\n';
    fout << cnt;

    fin.close();
    fout.close();

    return 0;
}