#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

int n;
int total = 0;
FILE *f, *g;
int cols[13];
int best[13];

void print_sol()
{
    for (int i = 0; i < n; i++)
        fprintf(g, "%d ", best[i] + 1);
    fprintf(g, "\n%d", total);
}

void save_sol(int cols[])
{
    total++;
    if (total == 1)
        for (int i = 0; i < n; i++)
            best[i] = cols[i];
}

bool check(int pos, int cols[]) 
{
    for (int i = 0; i < pos; i++)
    {
        if (cols[i] == cols[pos])
            return false;

        if (abs(cols[i] - cols[pos]) == abs(i - pos))
            return false;
    }

    return true;
}

void back(int p, int cols[])
{
    for (int i = 0; i < n; i++)
    {
        cols[p] = i;

        if (check(p, cols))
        {
            if (p == n - 1) 
            {
                save_sol(cols);
                return;
            }
            else
                back(p+1, cols);
        }
    }
}

int main()
{  
    f = fopen("damesah.in", "r");
    g = fopen("damesah.out", "w");

    fscanf(f, "%d", &n);

    back(0, cols);
    print_sol();

    fclose(f);
    fclose(g);

    return 0;
}