#include <cstdio>

using namespace std;

FILE *f, *g;

bool ok = 1;

int n, k;

int cnt;

int lin[15], col[15];

int diag1[15], diag2[15];

int stk[15];

int modul(int a)
{
    if(a < 0)
        return -a;

    return a;
}

void readFile()
{
    f = fopen("damesah.in", "r");

    fscanf(f, "%d", &n);

    fclose(f);
}

void printFile()
{
    g = fopen("damesah.out", "w");

    int i;

    for(i = 1; i <= n; i ++)
        fprintf(g, "%d ", stk[i]);

    fprintf(g, "\n");
}

bool valid()
{
    if(lin[k] == 1 || col[stk[k]] == 1 || diag1[stk[k] - k + n] == 1 || diag2[k + stk[k] - 1] == 1)
        return false;

    return true;
}

void solve()
{
    k = 1;

    while(k != 0)
    {
        if(stk[k] < n)
        {
            stk[k] ++;

            if(valid())
            {
               // printf("****%d %d\n", k, stk[k]);

                col[stk[k]] = lin[k] = diag1[stk[k] - k + n] = diag2[k + stk[k] - 1] = 1;

                /*for(int i = 1; i <= n; i ++)
                {
                    printf("%d %d\n", lin[i], col[i]);
                }

                for(int i = 1; i < 2 * n; i ++)
                    printf("+%d %d\n", diag1[i], diag2[i]);*/

                if(k == n)
                {
                    if(ok == 1)
                    {
                        ok = 0;

                        printFile();

                        cnt = 1;
                    }

                    else
                        cnt ++;

                    col[stk[k]] = lin[k] = diag1[stk[k] - k + n] = diag2[k + stk[k] - 1] = 0;
                }

                else
                {
                    k ++;

                    stk[k] = 0;
                }
            }
        }

        else
        {
            k --;

            col[stk[k]] = lin[k] = diag1[stk[k] - k + n] = diag2[k + stk[k] - 1] = 0;

           // printf("**********");
        }

        //printf("*%d %d\n", k, stk[k]);

       /* for(int i = 1; i <= n; i ++)
        {
            printf("%d %d\n", lin[i], col[i]);
        }

        for(int i = 1; i < 2 * n; i ++)
            printf("+%d %d\n", diag1[i], diag2[i]);*/
    }
}

void printResult()
{
    fprintf(g, "%d\n", cnt);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printResult();

    return 0;
}