#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;
}