#include <fstream>
#include <cmath>

using namespace std;

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

int n, nr, k, x[15];

int modul(int a)
{
    if(a < 0) return -a;
    return a;
}

void BKT(int k)
{
    if(k == n+1)
    {   if(!nr)
            {   for(int i=1; i<=n; i++) g << x[i] << ' ';
                g << '\n';
            }
        nr++;
    }
    else
        {   for(int i=1; i<=n; i++)
                {   bool ok = 1;
                    for(int j=1; j<k && ok; j++) if(x[j] == i || modul(x[j]-i) == modul(k-j)) ok = 0;
                    if(ok)
                        {   x[k] = i;
                            BKT(k+1);
                        }
                }
        }
}

int main()
{
    f >> n;
    BKT(1);
    g << nr << '\n';
    return 0;
}