#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <stdlib.h>
using namespace std;

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

int n,l=0;
vector<int> t; //solutiile;

bool valid(int k)
{
    for (int i=1;i<k;i++)
    {
        if(t[i]==t[k] || abs(t[k]-t[i])==(k-i)) return false;
    }
    return true;
}

bool solutie(int k)
{
    if (k==n) return true;
    return false;
}

void afisare()
{
    if (l==0)
    for (int i=1;i<=n;i++)
    {
        out<<t[i]<<' ';
    }
    l++;
}

void BK(int k)
{
    for (int i=1;i<=n;i++)
    {
        t[k]=i;
        if (valid(k))
        {
            if (solutie(k)) afisare();
                else BK(k+1);
        }
    }
}

main()
{
    in>>n;
    t.resize(n+1);
    t[n]=0;
    BK(1);
    out<<'\n'<<l;
}