#include <stdio.h>
#include <stdlib.h>
FILE *fin = NULL;
FILE *fout = NULL;
// void reset(int m[9][9])
// {
//     for (int i = 1; i < 9; i++)
//     {
//         for (int j = 1; j < 9; j++)
//         {
//             m[i][j] = 0;
//         }
//     }
// }
// void afisare(int m[9][9])
// {
//     for (int i = 1; i < 9; i++)
//     {
//         for (int j = 1; j < 9; j++)
//         {
//             printf("%d ", m[i][j]);
//         }
//         printf("\n");
//     }
//     reset(m);
// }
FILE *deschiderefisier(char *nume, char *type)
{
    FILE *fin = NULL;
    if ((fin = fopen(nume, type)) == NULL)
    {
        printf("eroare la deschiderea fisierului");
        exit(EXIT_FAILURE);
    }
    return fin;
}
void closefile(FILE *fin, char *name)
{
    if (fclose(fin))
    {
        printf("Eroare la inchiderea fisierului %s", name);
    }
}

void Init(int k, int *v) // k – vârful stivei
{
    v[k] = 0; // iniţializează/resetează, valoarea din // vârful stivei
}

int Succesor(int k, int n, int *v)
{
    if (v[k] < n)
    {
        v[k]++;
        return 1;
    }
    else
    {
        return 0;
    }
}
int Valid(int k, int *v)
{
    for (int i = 1; i < k; i++)
    {
        if (v[i] == v[k] || i == k || (abs(v[i] - v[k]) == abs(i - k)))
        {
            return 0;
        }
    }
    return 1;
}
int Solution(int k, int n)
{
    return (k == n);
}
void Print(int n, int *m, int *v, int a[9][9])
{

    // printf("%d : ", ++(*m));
    for (int i = 1; i <= n; i++)
    {
        fprintf(fout, "%d ", v[i]);
        a[i][v[i]] = 1;
    }
    printf("\n");
    // afisare(a);
}
void back(int n, int a[9][9])
{
    int v[10];
    int k = 1;
    int m = 0;
    int cnt = 0;
    Init(k, v);

    while (k > 0)
    {
        int isS = 0, isV = 0;
        if (k <= n)
        {
            do
            {
                isS = Succesor(k, n, v);
                if (isS != 0)
                {
                    isV = Valid(k, v);
                }
            } while (isS && !isV);
        }
        if (isS != 0)
        {
            if (Solution(k, n))
            {
                if (cnt == 0)
                {
                    Print(n, &m, v, a);
                }
                cnt++;
                // Print(n, &m, v, a);
                //  exit(EXIT_SUCCESS);
            }
            else
            {
                k++;
                Init(k, v);
            }
        }
        else
        {
            k--;
        }
    }
    fprintf(fout, "\n%d", cnt);
}
int main()
{
    int n;

    fin = deschiderefisier("damesah.in", "r");
    fout = deschiderefisier("damesah.out", "w+");
    // printf("n=");
    fscanf(fin, "%d", &n);
    // while (n > 8)
    //  {
    //      printf("N nu poate fi de cat maxim 8");
    //      printf("n=");
    //      scanf("%d", &n);
    //  }

    int m[9][9] = {0};
    // afisare(m);
    back(n, m);
}