#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int c[15],n,cnt = 0;
bool col[20],main_diag[20],sec_diag[20];
void afisare()
{
    int i;
    if(cnt > 0)
        return;
    else
    {
        for(i = 1; i <= n; i++)
            cout << c[i] + 1 << " ";
        cout << "\n";
    }
}
void bkt(int l,int n)
{
    int i,j;
    bool ok;
    if(l == n + 1)
    {
        afisare();
        cnt++;
    }
    else
    {
        for(int cu = 0; cu < n; cu++)
        {
            if ( !col[cu] && !main_diag[cu - l + n - 1] && !sec_diag[l + cu] ) {
                c[l] = cu;

                col[cu] = main_diag[cu - l + n - 1] = sec_diag[l + cu] = true;
                bkt(l + 1, n );
                col[cu] = main_diag[cu - l + n - 1] = sec_diag[l + cu] = false;
            }
        }
    }
}
int main()
{
    cin >> n;
    bkt(1,n);
    cout << cnt;
    return 0;
}