#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]]++;
        dif[k - rez[k] + offset]++;
        fr[rez[k]]++;

        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]]--;
            dif[k - rez[k] + offset]--;
            fr[rez[k]]--;
        }
    }
}

int main()
{
    in >> n;

    sah(1);

    out << cont << '\n';

    return 0;
}