#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;

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

const int NMAX = 55;

int v[NMAX];

int n, sol;

bitset<NMAX> C, DP, DS;

void backtr(int l)
{
    if(l == n+1)
    {
        if(!sol)
        {
            for(int c=1; c<=n; c++)
            {
                fout<<v[c]<<' ';
            }
            fout<<'\n';
        }
        sol++;
    }

    for(int c=1; c<=n; c++)
    {
        if(!C[c] && !DP[l - c + n] && !DS[l + c])
        {
            v[l] = c;
            C[c] = DP[l - c + n] = DS[l + c] = 1;
            backtr(l + 1);
            C[c] = DP[l - c + n] = DS[l + c] = 0;
        }
    }
}

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