#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int fvd1[55],fvd2[55],fvc[55],N,ok,sol;
vector<int> v;

void back(int n)
    {
        int i;
        if (n==N+1)
            {
                if (!ok)
                {
                    for(i=0;i<N;++i)
                    g<<v[i]<<" ";
                    g<<'\n';
                    ok=1;
                }
                ++sol;
            }
        else
        for (i=1;i<=N;++i)
            if (!fvc[i] && !fvd1[i-n+20] && !fvd2[i+n])
                {
                    ++fvc[i];
                    ++fvd1[i-n+20];
                    ++fvd2[i+n];
                    v.push_back(i);
                    back(n+1);
                    v.pop_back();
                    --fvc[i];
                    --fvd1[i-n+20];
                    --fvd2[i+n];
                }
    }


int main()
{
    f>>N;
    back(1);
    g<<sol;
    return 0;
}