#include <iostream>
#include <fstream>
#include <cmath>
#define NUM 15
int C[NUM], nrs, prima, sol[NUM], n;
using namespace std;
bool Valid(int k)
{
    for(int i = 1 ; i < k ; i ++)
    {
        if(C[i] == C[k])
            return false;
        if(k - i == abs(C[k] - C[i]))
            return false;
    }
    return true;
}
void copiere()
{
    for(int i = 1; i <= n; ++i)
        sol[i] = C[i];
}
void dame(int k)
{
    for(int i = 1; i <= n; ++i)
    {
        C[k] = i;
        if(Valid(k))
        {
            if(k == n)
            {
                if(!prima)
                {
                    copiere();
                    prima = 1;
                }
                nrs++;
            }
            else
                dame(k + 1);
        }
    }

}
int main()
{
    ifstream f("damesah.in");
    ofstream g("damesah.out");
    f >> n;
    dame(1);
    for(int i = 1; i <= n; ++i)
        g << sol[i] << " ";
    g << "\n" << nrs;
    f.close();
    g.close();
}