#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

vector <int> a;
vector <bool> q,d1,d2;
int n,x=0;
bool b=true;

void bk(int k)
{
    if (k==n)
    {
        if (b)
        {
            for (int i=0; i<n; cout << a[i]+1 << ' ',i++);
            cout << '\n';
            b=false;
        }
        x++;
        return;
    }
    for (int i=0; i<n; i++)
        if ((!q[i]) && (!d1[i-k+n-1]) && (!d2[k+i-1]))
        {
            q[i]=true;
            a[k]=i;
            d1[i-k+n-1]=true;
            d2[i+k-1]=true;
            bk(k+1);
            a[k]=-1;
            d2[i+k-1]=false;
            d1[i-k+n-1]=false;
            q[i]=false;
        }
}

main()
{
    cin >> n;
    a.resize(n);
    q.resize(n);
    d1.resize(n+n-1);
    d2.resize(n+n-1);
    for (int i=0; i<n; i++) a[i]=-1,q[i]=false;
    bk(0);
    cout << x;
}