#include <iostream>
#include <fstream>

#define MAX 13

using namespace std;

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

struct piece
{
    int row, column;
};

piece curr[MAX + 5];

int n, minLexi[MAX + 5], ans, row = 1;
bool column[MAX + 5];

bool check(int & row, int r, int c)
{
    for(int i = 1;i < row; ++i)
    {
        if(abs(r - curr[i].row) == abs(c - curr[i].column))
            return false;
    }
    return true;
}

void bkt()
{
    if(row > n)
    {
        if(minLexi[0] == 0)
        {
            for(int i = 1;i <= n; ++i)
                minLexi[i] = curr[i].column;
            minLexi[0] = 1;
        }
        ans++;
        return;
    }

    for(int i = 1;i <= n; ++i)
    {
        if(!column[i])
        {
            bool ok = check(row, row, i);
            if(ok)
            {
                column[i] = 1;
                curr[row].row = row, curr[row].column = i;
                row++;
                bkt();
                row--;
                column[i] = 0;
            }
        }
    }
}

int main()
{
    fin >> n;

    bkt();

    for(int i = 1;i <= n; ++i)
        fout << minLexi[i] << ' ';
    fout << '\n' << ans;

    fin.close(), fout.close();
    return 0;
}