#include <iostream>
#include <fstream>

using namespace std;

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

int n, cont = 0;
int sum[30], dif[30], rez[20], fr[20];
bool ok = 0;
const int offset = 14;

void printOrNot()
{
    if(!ok)
    {
        for(int i = 1; i <= n; i++)
            out << rez[i] << ' ';

        out << '\n';

        ok = 1;
    }

    cont++;
}

bool valid(int k)
{
    if(sum[k + rez[k]] == 0 && dif[k - rez[k] + offset] == 0 && fr[rez[k]] == 0)
    {
        sum[k + rez[k]] = 1;
        dif[k - rez[k] + offset] = 1;
        fr[rez[k]] = 1;

        return true;
    }

    return false;
}

void sah(int k)
{
    for(rez[k] = 1; rez[k] <= n; rez[k]++)
    {
        if(valid(k))
        {
            if(k == n)
                printOrNot();
            else
                sah(k + 1);

            sum[k + rez[k]] = 0;
            dif[k - rez[k] + offset] = 0;
            fr[rez[k]] = 0;
        }
    }
}

int main()
{
    in >> n;

    sah(1);

    out << cont << '\n';

    return 0;
}