#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

int v[40], N, c, fr1[40], fr2[40], fr3[40];

void back (int i)
{
    if (i > N)
    {
        if(c==0)
        {
            for(int k=1; k<i-1; k++) out<<v[k]<<' ';
            out<<v[i-1]<<'\n';
        }
        c++;
    }
    else
    {
        for (v[i] = 1; v[i] <= N; v[i]++)
        {
            if (fr1[v[i]] == 0 && fr2[i+v[i]] == 0 && fr3[i-v[i]+20] == 0){
                fr1[v[i]]++;
                fr2[i+v[i]]++;
                fr3[i-v[i]+20]++;
                back(i+1);
                fr1[v[i]]--;
                fr2[i+v[i]]--;
                fr3[i-v[i]+20]--;
            }
        }
    }
}

int main()
{
    in >> N;
    back(1);
    out << c;
    return 0;
}