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

bool ok;
int n,k;

vector <char> V;

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

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

        /// dama cu care o verific pe cea pe care vreau sa o pun
        char l1=V[i];
        char c1=i;

        /// dama pe care incercam sa o punem
        char l2=x;
        char 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 ((char)V.size()==n)
    {
        if (ok==0)
        {
            ok=1;
            for (char i=0; i<(char) V.size(); i++)
                cout << (int) V[i] << " ";
            cout << endl;
        }
        k++;
        return;
    }

    for (char 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;
}