#include <bits/stdc++.h>
using namespace std;

int ok,k,n;
vector <int> V;

void fast ()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
}

bool free (int x)
{
    /// verific daca toate damele deja puse, nu ataca dama pe care vreau sa o pun la linia x
    for (int i=0; i<(int)V.size(); i++)
    {
        if (x==V[i])
            return false;
        int l1=V[i];
        int c1=i;
        int l2=x;
        int c2=V.size();

        /// diagonala principala
        if (l1-c1==l2-c2)
            return false;

        /// diagonala secundara
        if (l1+c1==l2+c2)
            return false;

    }
    return true;
}

void bkt ()
{
    if ((int)V.size()==n)
    {
        if (ok==0)
        {
            ok=1;
            for (int i=0; i<(int) V.size(); i++)
                cout << V[i] << " ";
            cout << endl;
        }
        k++;
        return;
    }

    for (int i=1; i<=n; i++)
    {
        if (free(i))
        {
            V.push_back(i);
            bkt();
            V.pop_back();
        }
    }
}

int main()
{
    fast();
    freopen("damesah.in","r", stdin);
    freopen("damesah.out","w", stdout);

    cin >> n;
    bkt();
    cout << k;
    return 0;
}