#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f ("damesah.in");
ofstream g ("damesah.out");
int x[13], solutie[13];
void tiparesteSolutie (int n)
{
    for(int i=1; i<=n; i++)
        solutie[i]=x[i];
}

bool eValid (int k)
{
    for(int i=1; i<k; i++)
    if((x[i]==x[k])||(k-i==abs(x[k]-x[i]))) return 0;
    return 1;
}

int backtracking (int n)
{
    int esolutie, k, nrsolutii=0, prima=1;
    k=1; x[k]=0;
    while (k>0)
    {
        esolutie=0;
        while ((x[k]<n) && (!esolutie))
        {
            x[k]++;
            esolutie=eValid(k);
        }
        if (!esolutie) k--;
        else
        {
            if (k==n)
            {
                if(prima)
                {
                    tiparesteSolutie(n);
                    prima=0;
                }
                nrsolutii++;
            }
            else {k++; x[k]=0;}

        }
    }
    return nrsolutii;
}

int main()
{
    int n, k, esolutie;
    f>>n;
    int nrsolutii=backtracking(n);
    for(int i=1; i<=n; i++)
        g<<solutie[i]<<" ";
    g<<"\n"<<nrsolutii;
}