#include <bits/stdc++.h>
#define N 15
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int x[N];
int n;
bool viz[N];
bool diag1[2*N];
bool diag2[2*N];

/*
5----
45---
345--
2345-
12345
matrice basic

5 1    1     n-dif

4 1    2
5 2    2

3 1    3
4 2    3
5 3    3

56---
456--
345--
2345-
12345

1 2   6
2 3   6
3 4   6
4 5   6

1 3   7
2 4   7
3 5   7
*/

void afisare()
{
    int i;
    for(i=1;i<=n;++i)fout<<x[i]<<" ";
}

bool gata;
int ct;

void backt(int k)
{
    int i;
    for(i=1;i<=n;++i)
        if(!viz[i]&&!diag1[n-k+i]&&!diag2[2*n-k-i+1])
    {
        viz[i]=1;
        diag1[n-k+i]=1;
        diag2[2*n-k-i+1]=1;
        x[k]=i;
        if(k<n)backt(k+1);
            else if(gata==0)
            {
                afisare();
                gata=1;
                ct++;
            }
            else ct++;

        diag1[n-k+i]=0;
        diag2[2*n-k-i+1]=0;
        viz[i]=0;
    }
}

int main()
{
    fin>>n;
    backt(1);
    fout<<"\n";
    fout<<ct;




    return 0;
}