#include <stdio.h>
#define maxn 20
using namespace std;

int poz[maxn], uzcol[maxn], d1[maxn << 1], d2[maxn << 1], n, sol = 0;
bool first = true;


void backt(int line)
{
    int i;

    if(line == n + 1)
     {
        if(first)
        {
            first = false;

            for(i = 1; i <= n; i++)
                printf("%d ", poz[i]);

            printf("\n");
        }

        sol++;
     }
     else
        {
            for(i = 1; i <= n; i++)
                if(!uzcol[i] && !d1[line - i + n] && !d2[line + i])
                {
                    poz[line] = i;

                    uzcol[i] = d1[line - i +n] = d2[line + i] = 1;

                    backt(line + 1);

                    uzcol[i] = d1[line - i +n] = d2[line + i] = 0;

                }
        }
}



int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d", &n);

    backt(1);

    printf("%d", sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}