#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

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

int n, C[101], uz[101], M[101][101], nrsol;
int i, x=1, y;

void afisare()
{
    int i, j;
    for (i=1; i<=n; i++)
    {
        fout<<M[1][i]<<" ";
    }
    fout<<'\n';
    fout<<nrsol<<'\n';
}

void copiere()
{
    for (y=1; y<=n; y++)
        M[x][y]=C[y];
    x++;

}

void Regine(int k)
{
    int ok;
    int i, j;

    if (k==n+1)
    {
        nrsol++;
        copiere();
        return;
    }

    for (i=1; i<=n; i++)
    {
        ok=1;
        if (!uz[i])
        {   for (j=1; j<k; j++)
                if (abs (C[j]-i)==(k-j))
                    ok=0;
        }
        else ok=0;

        if (ok)
        {
            C[k]=i;
            uz[i]=1;
            Regine(k+1);
            uz[i]=0;
        }
    }
}

int main()
{
    fin>>n;
    Regine(1);
    afisare();
    return 0;
}