#include <fstream>
#include <cmath>
using namespace std;
 
ifstream fin("damesah.in");
ofstream fout("damesah.out");
 
#define DIM 20
int n, nr_sol;
int sol[DIM];
bool first = true;
bool column[DIM];
bool d1[DIM << 1];
bool d2[DIM << 2];
 
 
void Back(int k);
bool Check(int k, int i);
 
int main()
{
    fin >> n;
    Back(1);
 
    fout << nr_sol;
}
 
 
void Back(int k)
{
    if (k > n)
    {
        if (first)
        {
            first = false;
            for (int i = 1; i <= n; ++i)
                fout << sol[i] << ' ';
            fout << '\n';
        }
        nr_sol++;
        return;
    }
 
    for (int i = 1; i <= n; ++i)
        if (Check(k, i))
        {
            sol[k] = i;
            column[i] = true;
            d1[i - k + n] = true;
            d2[k + i] = true;
            Back(k + 1);
            d2[k + i] = false;
            d1[i - k + n] = false;
            column[i] = false;
            sol[k] = 0;
        }
};
 
 
bool Check(int k, int i)
{
    if (column[i] || d1[i - k + n] || d2[i + k])
        return false;
     
    return true;
};