#include <fstream>
#include <math.h>
using namespace std;

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

void back(int k);
void afis();
int n, v[15], cnt;
bool dig1[29], dig2[29], col[15];

int main()
{
    fin>>n;
    back(1);
    fout<<cnt;
    fin.close();
    fout.close();
    return 0;
}

void afis()
{
    for (int i = 1; i <= n; i++)
        fout<<v[i]<<" ";
    fout<<"\n";
}

void back(int k)
{
    if (k == n + 1)
    {
        if (cnt == 0)
        {
            afis();
        }
        cnt++;
    }
    else
    {
        /*care citeste asta sa stie ca i-am impartasit durerea in a intelege acest algoritm :)
        dig1 si dig2 sunt vectori care memoreaza numarul de diagonale principale si secundare
        */
        for(int i = 1; i <= n; i++)
        {
            if(!col[i] && !dig1[n + i - k] && !dig2[i + k])
            {
                v[k] = i;
                col[i] = 1; dig1[n + i - k] = 1; dig2[i + k] = 1;
                back(k + 1);
                col[i] = 0; dig1[n + i - k] = 0; dig2[i + k] = 0;
            }
        }
    }
}