#include <iostream>
#include <fstream>
#define dm 101
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
bool lin[dm], d1[dm], d2[dm];
int n, c, nrperm, st[dm];
void afis()
{
    for(int i = 1; i <= n; i++)
        fout << st[i] << " ";
}
void dame(int niv)
{
    if( niv == n + 1 )
    {
        if( nrperm == 0 )
        {
            afis();
        }
        nrperm++;
        return;
    }
    for( int j = 1; j <= n; j++)
    {
        if(!lin[j] && !d1[niv + j] && !d2[niv - j + n])
        {
            st[niv] = j;
            lin[j] = 1;
            d1[niv + j] = 1;
            d2[niv - j + n] = 1;
            dame(niv + 1);
            lin[j] = 0;
            d1[niv + j] = 0;
            d2[niv - j + n] = 0;
        }
    }
}
int main()
{
    fin >> n;
    dame(1);
    fout << "\n" << nrperm;
    return 0;
}