#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 13

// void printTable(int table[N][N], int size)
// {
//     for(int i = 0; i < size; i++)
//     {
//         for(int j = 0; j < size; j++)
//         {
//             printf("%d ", table[i][j]);
//         }
//         printf("\n");
//     }
//     printf("\n");
// }

void printConfiguration(int* configuration, int size, FILE* fout)
{
    for(int i = 0; i < size; i++)
        fprintf(fout, "%d ", configuration[i]);
    fprintf(fout, "\n");
}

bool isSafe(int table[N][N], int row, int column, int size)
{
    // check the main diagonal
    // we add +1 because otherwise we would be comparind against the base
    // element on that line
    for(int i = row + 1, j = column + 1; i < size && j < size; i++, j++)
    {
        if(table[i][j] == 1)
            return false;
    }

    // check the secondary diagonal
    for(int i = row + 1, j = column - 1; i < size && j >= 0; i++, j--)
    {
        if(table[i][j] == 1)
            return false;
    }

    // check the column
    for(int i = row + 1, j = column; i < size; i++)
    {
        if(table[i][j] == 1)
            return false;
    }

    return true;
}

bool isSafeTable(int table[N][N], int size)
{
    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            if(table[i][j] == 1)
            {
                if(!isSafe(table, i, j, size))
                {
                    return false;
                }
            }
        }
    }
    return true;
}

void _getQueens(int table[N][N], int size, int queens, int row,
    int* firstConfiguration, int* solutions, FILE* fout)
{
    if(queens == size)
    {
        if(isSafeTable(table, size))
        {
            (*solutions)++;
            if((*solutions) == 1)
                printConfiguration(firstConfiguration, size, fout);
        }
        return;
    }

    for(int i = 0; i < size; i++)
    {
        table[row][i] = 1;
        firstConfiguration[row] = i + 1;
        if(isSafeTable(table, size))
        {
            _getQueens(table, size, queens + 1, row + 1, firstConfiguration,
                solutions, fout);
        }
        table[row][i] = 0;
    }
}

void generateQueens(int size, FILE* fout)
{
    int table[N][N] =
    {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    int solutions = 0;
    int firstConfiguration[N];

    _getQueens(table, size, 0, 0, firstConfiguration, &solutions, fout);

    fprintf(fout, "%d", solutions);
}

int main()
{
    FILE* fin  = fopen("damesah.in", "r");
    FILE* fout = fopen("damesah.out", "w");

    int size;
    fscanf(fin, "%d", &size);

    generateQueens(size, fout);

    fclose(fin);
    fclose(fout);

    return 0;
}