#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N, V[15], Nr, C[15], D1[40], D2[40];

void Afisare()
{
    for(int i = 1; i <= N; i++)
        fout << V[i] << " ";

    fout << '\n'; Nr = 1;
}

void BKT(int K)
{
    for(int i = 1; i <= N; i++) {
        V[K] = i;

        if(D1[K - i + N] || D2[i + K] || C[i]) continue;

        D1[K - i + N] = C[i] = D2[i + K] = 1;

        if(K < N)
            BKT(K + 1);
        else if(Nr)
            Nr++;
        else
            Afisare();

        D1[K - i + N] = C[i] = D2[i + K] = 0;
    }
}

int main()
{
    fin >> N;
    BKT(1);
    fout << Nr;

    return 0;
}